Let $A$ be a symmetric positive definite invertible real valued matrix. Then we can write $A=SS^T$ where $S$ is a lower triangular matrix with positive entries on its diagonal. This decomposition is called the Cholesky decomposition.

How do we know that the entries of $S$ are themselves real-valued? I need this property in order to solve a problem related to the Courant-Fischer min-max theorem.

  • $\begingroup$ you should add the symmetric condition $\endgroup$ – Ahmad Bazzi Dec 13 '19 at 11:30
  • $\begingroup$ $S$ can be computed by forward substitution. The substitution process does not require field extension. Therefore $S$ is real. $\endgroup$ – user1551 Dec 13 '19 at 13:52
  • $\begingroup$ What is "forward substitution" ? $\endgroup$ – Christian Singer Dec 13 '19 at 14:43
  • $\begingroup$ "Forward substitution" refers to the practice of solving an indexed set of equations iteratively, in which we substitute the solution to the $(k-1)$-th equation into the $k$-th equation and solve the latter. You may think of it as mathematical induction. $\endgroup$ – user1551 Dec 14 '19 at 11:12

Let $A_k$ be the leading principal $k\times k$ submatrix of $A$. Clearly, $A_1=S_1S_1^T$ where $S_1=\sqrt{A_1}$ is a real $1\times1$ lower triangular matrix. Now suppose that for some $k$, $A_{k-1}=S_{k-1}S_{k-1}^T$ for some real lower triangular matrix $S_{k-1}$. Since $A_{k-1}$ is positive definite, $S_{k-1}$ is nonsingular. Also, as $u^TA_ku>0$ for every nonzero vector $u$, if we write $A_k=\pmatrix{A_{k-1}&v_k\\ v_k^T&a_k}$ and put $u=(-v_k^TA_{k-1}^{-1},\,1)^T$, we obtain $a_k-v_k^TA_{k-1}^{-1}v_k>0$. Therefore the equation $$ \pmatrix{A_{k-1}&v_k\\ v_k^T&a_k} =\pmatrix{S_{k-1}&0\\ x^T&s}\pmatrix{S_{k-1}^T&x\\ 0&s}\tag{1} $$ has a unique solution $x=S_{k-1}^{-1}v_k,\,s=\sqrt{a_k-x^Tx}=\sqrt{a_k-v_k^TA_{k-1}^{-1}v_k}$. This means $A_k=S_kS_k^T$ for some real lower triangular matrix $S_k$. So, if we start from $A_1$ and keep solving $(1)$ for $k=2,3,\ldots$, we see that $A=SS^T$ for some real lower triangular matrix $S$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.