This is a exercise on my numerical analysis textbook:
Suppose $\mathbf A$ is a positive-definite symmetric matrix, and the Cholesky decomposition is of the form $\mathbf {A} =\mathbf {LL}^{T}$, where $\mathbf L$ is a lower triangular matrix.
Prove the following statements:$$l_{ii}^2 \geq \min\frac{\mathbf x^T \mathbf A \mathbf x}{\mathbf x^{T} \mathbf x} = \frac{1}{\| \mathbf L^{-T}\|_2^2} \tag{1}$$
$$l_{ii}^2\leq \max\frac{\mathbf x^T \mathbf A \mathbf x}{\mathbf x^{T} \mathbf x} = \| \mathbf L^{T} \|_2^2 \tag{2}$$
$$\| \mathbf L^{-T} \|_2^2 \cdot \| \mathbf L^{T} \|_2^2 \geq \max_{1 \leq i,j\leq n}\frac{|l_{ii}|}{|l_{jj}|} \tag{3}$$
where $\mathbf L^{-T}$ means the inverse and transpose of $\mathbf L$.
According the theorem of Rayleigh (Rayleigh quotient), I noted that
$$\|\mathbf L^{T}\|_2^2 = \lambda_{\max} (\mathbf A) = \max\frac{\mathbf x^T \mathbf A \mathbf x}{\mathbf x^{T} \mathbf x}$$
$$\frac{1}{\| \mathbf L^{-T} \|_2^2} = \lambda_{\min} (A) = \min\frac{\mathbf x^T \mathbf A \mathbf x}{\mathbf x^{T} \mathbf x}$$
However, I cannot find the relationship between the eigenvalues of $\mathbf A$ and the diagonal entries of $\mathbf L$, namely, $l_{ii}.$ Can anyone offer me a help? Thank you in advance!
Best Answer
Using properties of $\|\cdot\|_2$ norm we have $$\|\mathbf{L}^T\|_2^2 = \|\mathbf{L}\|_2^2 = \max_{\|x\|_2=1}\|\mathbf{L}x\|_2^2 \geq \|\mathbf{L}e_i\|_2^2 = \sum_{j=i}^n l_{ji}^2 \geq l_{ii}^2 \,,$$ for any $i$. Here $e_i$ denotes the $i$-th column of identity matrix. Similarly, $$\|\mathbf{L}^{-T}\|_2^2 = \|\mathbf{L}^{-1}\|_2^2 \geq \|\mathbf{L}^{-1}e_j\|_2^2 \geq l_{jj}^{-2} \,,$$ for any $j$, because $\mathbf{L}^{-1}$ is lower triangular with $l_{11}^{-1},\ldots,l_{nn}^{-1}$ on its diagonal. This proves the first two statements.
To prove the third statement, we multiply the previous two inequalities and take maximum over $1\leq i, j\leq n$ to obtain $$\|\mathbf{L}^{-T}\|_2^2\|\mathbf{L}^{T}\|_2^2 \geq \max_{1\leq i,j\leq n}\frac{l_{ii}^2}{l_{jj}^2} \geq \max_{1\leq i,j\leq n}\frac{|l_{ii}|}{|l_{jj}|} \,.$$ The last inequality follows because maximum in both cases is obtained for some $i,j$ such that $|l_{ii}||l_{jj}|^{-1}\geq1$, for which $l_{ii}^2l_{jj}^{-2}\geq |l_{ii}||l_{jj}|^{-1}$