A matrix is positive semidefinite iff it can be written in the form $X'X$

Question

I know the fact that a matrix is positive semidefinite if and only if it can be written in the form $X'X$. But how to prove it?

Thanks in advance.

Answer 1

OK, first off, I am assuming the notation $X'$ our OP Ian uses in his question is in fact, as I asked in my comment, the same as the conventional $X^T$, which I shall deploy throughout.

It is easy to see that a matrix $A$ such $A = X^TX$ is positive definite; we have

$\langle v, Av \rangle = \langle v, X^TXv \rangle = \langle Xv, Xv \rangle \ge 0. \tag{1}$

However, going the other way is much more difficult. And the reason it is much more difficult is:

IT IS FALSE that every positive semi-definite matrix $A$ can be written $A = X^TX$.

However,

IT IS TRUE that every symmetric positive semi-definite matrix $A$ can be so written.

To see this, suppose $A = A^T$; then $A$ may be diagonalized by some orthogonal matrix $O$: $O^TAO = \Lambda = \mathrm{diag} (\lambda_1, \lambda_2, . . . , \lambda_n)$, where $n$ is the size of $A$. Then for any vector $x$, set $y = O^Tx$, so that $Oy = OO^Tx = x$; then

$$ \langle x, Ax \rangle = \langle Oy, AOy \rangle = \langle y, O^TAOy \rangle = \langle y, \Lambda y \rangle, \tag{2} $$

so that taking $y = (y_1, y_2, . . . , y_n)^T$ yields

$$ \langle x, Ax \rangle = \sum_1^n \lambda_i y_i^2; \tag{3} $$

this shows we must have all $\lambda_i \ge 0$, hence we can take

$$ \Lambda^{\frac{1}{2}} = \mathrm{diag}\left(\lambda_1^{\frac{1}{2}}, \lambda_2^{\frac{1}{2}},\ldots, \lambda_n^{\frac{1}{2}}\right), \tag{4} $$

and setting $X = O\Lambda^{\frac{1}{2}} O^T$, we see that

$$ X^TX = O^{TT} \left(\Lambda^{\frac{1}{2}T} O^T O \Lambda^{\frac{1}{2}}\right) O^T = O \Lambda O^T = A, \tag{5} $$

establishing the desired result. Note we have exploited the symmetry of $\Lambda^{\frac{1}{2}}$ in performing this calculation.

It should be observed that $A = X^TX$ implies $A$ symmetric: $A^T = (X^TX)^T = X^TX^{TT} = X^TX = A$; thus a positive semi-definite $A$ would automatically be symmetric if the assertion $A= X^TX$ were true.

To see that $A$ positive semi-definite is not sufficient to force $A = X^TX$, consider the $2 \times 2$ matrix

$$A = \begin{bmatrix} \lambda & \epsilon \\ 0 & \lambda \end{bmatrix}, \tag{6} $$

and let $v = (x,y)^T$. Then

$ \langle v, Av \rangle = (x, y) \begin{bmatrix} \lambda & \epsilon \\ 0 & \lambda \end{bmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \lambda (x^2 + y^2) + \epsilon xy \tag{7} $

I claim that, at least for $\lambda > 0$ and $\vert \epsilon \vert \le \lambda$,

$\lambda (x^2 + y^2) + \epsilon xy \ge 0 \tag{8}$

for all $(x, y)^T$. To see this, note that we can, without loss of generality, take $\vert x \vert \le \vert y \vert$, since the quadratic form $\lambda (x^2 + y^2) + \epsilon x y$ is symmetric in $x$ and $y$. Then we have

$\vert \epsilon x y \vert = \vert \epsilon \vert \vert x \vert \vert y \vert \le \lambda \vert y \vert ^2 = \lambda y^2, \tag{9}$

or

$- \lambda y^2 \le \epsilon x y \le \lambda y^2, \tag {10}$

whence

$0 \le \lambda y ^2 + \epsilon x y \le \lambda (x^2 + y^2) + \epsilon x y, \tag {11}$

showing that $A$ is positive semi-definite. But there is no similarity transformation which diagonalizes $A$; indeed, if for some nonsingular $W$, $WAW^{-1}$ were diagonal, we would have to have $WAW^{-1} = \lambda I$, since the characteristic polynomial of a matrix is a similarity invariant. But then we would have $W(A - \lambda I)W^{-1} = 0$; but this is impossible since $A - \lambda I = \epsilon N$, where $N = [\delta_{i, i + 1}]$ is a non-vanishing, albeit nilpotent, matrix; it cannot be "similaritized" into vanishing.

In closing: certain generaizations may be possible: if $A$ is an $n \times n$ matrix of the form

$A = \lambda I + \epsilon N, \tag{12}$

then $A$ is positive semi-definite provided $\vert \epsilon \vert \le \frac{\lambda}{n - 1}$ for $\lambda > 0$; furthermore $A$ can't be diagonalized; the arguments are essentially the same as those given above.

Sorry about all the false starts, false alarms, and repetitive editing.

Hope this helps. Cheers.