3
$\begingroup$

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.

$\endgroup$

closed as off-topic by Matemáticos Chibchas, Paul Frost, blub, Javi, metamorphy Aug 4 at 14:49

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Paul Frost, blub, Javi, metamorphy
If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ It would be useful to know how you came across the problem and whether or not you have tried to solve it yourself, and if so what you did and why/where you still need help. $\endgroup$ – Ben Millwood Sep 3 '13 at 3:30
  • 1
    $\begingroup$ @Ian: I take it by $X'$ you mean what is usually written $X^T$, the adjoint or transpose of$X$, i.e., $X^T_{ij} = X_{ji}$, where the $X = [X_{ij}]$? $\endgroup$ – Robert Lewis Sep 3 '13 at 4:28
  • $\begingroup$ Here you go, straight from Wikipedia. $\endgroup$ – Omnomnomnom Sep 3 '13 at 4:35
  • $\begingroup$ Use the spectral theorem to reduce to the diagonal case. $\endgroup$ – Qiaochu Yuan Sep 3 '13 at 7:56
7
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Blah! hit that "Post" button by mistake again! Damn this 'droid! Damn these beefy, guitar pickin' fingers! But hey, 's'all good! I'll just edit this thing into submission! Stay tuned . . . ;) $\endgroup$ – Robert Lewis Sep 3 '13 at 10:31
  • $\begingroup$ Blast! Did it again! Almost there, hang on, final edits pending! $\endgroup$ – Robert Lewis Sep 3 '13 at 17:43
  • $\begingroup$ I tried fixing the LaTeX, please check to ensure I did not add an error. $\endgroup$ – Avraham Sep 3 '13 at 17:51
  • $\begingroup$ @Av'racham: wil do. $\endgroup$ – Robert Lewis Sep 3 '13 at 19:45
  • $\begingroup$ Still needs a little more work. Comong, coming . . . SOON! $\endgroup$ – Robert Lewis Sep 3 '13 at 19:53
0
$\begingroup$

Let me provide a rather elementary method for real symmetric matrix $A$ (since OP didn't mention in which field the entries are):

First, suppose that a real symmetric matrix $A$ is positive semidefinite, then we can find an invertible matrix $P$, such that $$P^{T}AP=\operatorname{diag}\{\underbrace{1,1,...,1}_r,\underbrace{0,0,...,0}_{n-r}\}.$$ Multiply $(P^{T})^{-1}=(P^{-1})^T$ and $P^{-1}$ on the left and right side of the RHS, we have $$ A=(P^{-1})^{T}\operatorname{diag}\{\underbrace{1,1,...,1}_r,\underbrace{0,0,...,0}_{n-r}\}P^{-1} .$$ If we force the last $(n-r)$ rows of $P^{-1}$ to be zero, and denote the new matrix by $\tilde P^{-1}$, then $$ A=(\tilde P^{-1})^{T}\tilde P^{-1} $$ and we are done.

To show the converse, it suffices to note that if $A=P^{T}P$, then for every $x=(x_1,x_2,...,x_n)\ne 0$ we have $$xAx^{T}=xP^{T}Px^{T}=(xP^{T})(xP^{T})^{T}\ge 0.$$

$\endgroup$

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