Finding first nonzero element per row after Choleski decomposition

Question

For a symmetric and positive definite matrix $A$, we define the numbers $f_{i}(A), i=1,...,n$ as follows:

$f_{i}(A)=min${${j|a_{i,j}\neq0}$}

Show that for the Choleski decomposition $A=LL^{T}$ the equality $f_{i}(L)=f_{i}(A)$ holds for $i=1,...,n$.

Answer 1

This can be proven by induction for all rows $i=1,...,n$. First, we show the implication for all first elements in every row in matrix $A$, namely: $$a_{i,1}=0\iff l_{i,1}=0$$ Then we show assuming that for all rows $i=1,...n$ that $a_{i,k}=0$ with $k=1,...,j-1$ implies: $$a_{i,j}=0\iff l_{i,j}=0$$

By induction it is then proven that if the first element in any row in matrix $A$ is equal to zero, the first element in the matrix $L$ must also be equal to zero. If so, this holds for every next element in the row, implying that the first nonzero element in every row in matrix $A$ corresponds to the first nonzero element in every row in matrix $L$. We not have to worry about any element right from the main diagonal in the matrices $A$ and $L$, since $a_{i,i}=\sum_{k=1}^{i}c_{i,k}^{2}>0$ and $l_{i,i}=1$ for $i=1,...,n$ by definition of a Choleski decomposition.

Let $i\in${$1,...,n$} be random, then $a_{i,1}=l_{i,1}$, thus $a_{i,1}=0\iff l_{i,1}=0$.

Let $j\in${$1,...,i$} be random and assume that $a_{i,m}=0$ for $m=1,...,j-1$. We find the element $a_{i,j}=\sum_{k=1}^{n}l_{i,k}l_{k,j}^{T}=\sum_{k=1}^{n}l_{i,k}l_{j,k}$ with $l_{i,m}=0$ and $l_{i,j}=0$ for $j>i$. Thus we find $a_{i,j}=l_{i,j}l_{j,j}=l_{i,j}$ and may assume that $f_{i}(L)=f_{i}(A)$.