1
$\begingroup$

Recall the Cholesky Theorem on $LL^{T}$-Factorization:

Theorem: If $A$ is a real, symmetric, and positive definite matrix, then it has a unique factorization, $A=LL^{T}$, in which $L$ is lower triangular with a positive digonal.

I need to use the Cholesky Theorem to show that the following two propertie sof a symmetric matrix $A$ (i.e., a matrix where $A = A^{T}$) are equivalent:

  1. $A$ is positive definite (i.e., $x^{T}Ax > 0$ for every nonzero vector $x$).
  2. There exists a linearly independent set of vectors $x^{(1)},x^{(2)},\cdots,x^{(n)}$ in $\mathbb{R}^{n}$ such that $A_{ij} = \left( x^{(i)}\right)^{T}\left( x^{(j)} \right)$.

I kind of see where the second part comes from, since if $A$ were a matrix we got as a result of multiplying together two other matrices $B$ and $C$, then each entry $A_{ij}$ would be the product of a row vector and a column vector. But, I'm really kind of lost as to how to prove this.

$\endgroup$
  • $\begingroup$ Not entire sure where you're stuck. 1 follows from 2 fairly easily, and if you're able to use the Cholesky factorization, 2 follows from the symmetry assumption and 1 by choosing the $x^{(i)}$ to be the columns of $L$. $\endgroup$ – icurays1 Dec 16 '15 at 1:03
1
$\begingroup$

$1 \implies 2$: If $A$ is positive definite, let $LL^\top$ be as in the Cholesky theorem. Then let $x^{(i)}$ be the $i$th row of $L^\top$.

$2 \implies 1$: If $X$ is the matrix with columns $x^{(i)}$, then $A=X^\top X$. This is positive definite because $x^\top A x = x^\top XX^\top x = \|X^\top x\|^2 \ge 0$, with equality if and only if $x=0$ since $X$ is full rank.

$\endgroup$
  • $\begingroup$ how do we know the entries in the rows of $L^{T}$ are linearly independent? $\endgroup$ – ALannister Dec 16 '15 at 3:56
  • $\begingroup$ @JessyCat $L$ is triangular with positive diagonal entries. $\endgroup$ – angryavian Dec 16 '15 at 3:57
  • $\begingroup$ so it's non-singular, hence the columns of $L^{T}$ form a basis for $\mathbb{R}^{n}$? $\endgroup$ – ALannister Dec 16 '15 at 3:58
  • $\begingroup$ @JessyCat Yes, that's right. $\endgroup$ – angryavian Dec 16 '15 at 3:59
  • 1
    $\begingroup$ @JessyCat Sorry there was a typo, it should have been $\|X^\top x\|^2$. Anyway, the norm of a vector $v$ can be written as $\|v\|=\sqrt{v^\top v}$. $\endgroup$ – angryavian Dec 16 '15 at 6:48

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.