I am trying to prove the following property on symmetric positive definite matrices:
Problem
Let $A \in \mathbb{R}^{n\times n}$ be a symmetric positive definite matrix. Suppose that the gaussian elimination method without pivoting is being applied. Prove that after $k$ steps of gaussian elimination, $${a_{ii}}^k \leq {a_{ii}}^{k-1}$$
Solution
I've tried to take the following approach:
Let $1 \leq k \leq n$.
If $i \leq k$, then after the $k-th$ step of gaussian elimination, $$a_{ii}^k = a_{ii}^{k-1}$$ so the inequality is satisfied.
If $ k+1 \leq i \leq n$, then $$a_{ii}^k = a_{ii}^{k-1} – \dfrac{a_{ik}^{k-1}}{a_{kk}^{k-1}}a_{ki}^{k-1}$$
Since the submatrix $A_{{n-k}{n-k}}$ located at the bottom right after $k$ steps of gaussian elimination is also symmetric positive definite, it satisfies that each $d_{jj} > 0$, where $d_{jj}$ is a diagonal element of $A_{(n-k)(n-k)}$, then $$a_{ii}^k > 0$$
At this point I got stuck, I don't know how to arrive to the inequality I want to. I would really appreciate any suggestions.
Best Answer
As you have stated, we have $$ a_{ii}^k = a_{ii}^{k-1} - \dfrac{a_{ik}^{k-1}}{a_{kk}^{k-1}}a_{ki}^{k-1} = a_{ii}^{k-1} - \dfrac{(a_{ik}^{k-1})^2}{a_{kk}^{k-1}}. $$ We always have $\frac{(a_{ik}^{k-1})^2}{a_{kk}^{k-1}} \geq 0$. It follows that $$ a_{ii}^k = a_{ii}^{k-1} - \frac{(a_{ik}^{k-1})^2}{a_{kk}^{k-1}} \geq a_{ii}^{k-1} - 0 = a_{ii}^{k-1}, $$ which was what we wanted.