# Easiest way to show positive semi-definite equivalence

For an $$x \in \mathbb{R}^n$$, and $$n$$-by-$$n$$ identity matrix $$I_n$$, we are given that $$\begin{pmatrix} I_n & x \\ x^T & 1 \end{pmatrix} \succeq 0.$$

What is the easiest way to show that $$\begin{pmatrix} 1 & x^T \\ x & I_n \end{pmatrix} \succeq 0$$ holds?

• Symmetric permutation? – user251257 Mar 22 at 18:37
• seems so. is there such a theory which concludes? – independentvariable Mar 22 at 18:40
• Schur complement? – user251257 Mar 22 at 19:02
• They dont reduce to the same condition, do they? – independentvariable Mar 22 at 19:22

This is due to the identity

$$\underbrace{\begin{pmatrix} 0_{1,n} & 1 \\ I_n & 0_{n,1} \end{pmatrix}}_{J^T} \underbrace{\begin{pmatrix} I_n & x \\ x^T & 1 \end{pmatrix}}_{A} \underbrace{\begin{pmatrix} 0_{n,1} & I_n \\ 1 & 0_{1,n} \end{pmatrix}}_{J} = \underbrace{\begin{pmatrix} 1 & x^T \\ x & I_n \end{pmatrix}}_{B}$$

(notation $$0_{m,n}$$ is for a zero block with $$m$$ lines and $$n$$ columns).

Indeed, $$J$$ being a permutation matrix, it is an orthogonal matrix, with $$J^T=J^{-1}$$. We can conclude that $$A$$ and $$B$$ are similar, thus have the same spectrum (Similar matrices have the same eigenvalues with the same geometric multiplicity) with positive eigenvalues, thus are both semi-definite positive.

Besides, $$A$$ being symmetric, one can conclude from $$J^TAJ=B$$ that $$B$$ is symmetric as well.

Appendix : There is a pending question : is there a criteria on $$x$$ for positive semi-definiteness of $$A$$. ? The answer is yes :

$$A$$ is semi-definite positive iff $$\|x\| \leq 1$$.

This is due, as we are going to see it, to an analysis of the rather particular spectrum of $$A$$. Let us obtain it explicitly.

First of all, let us establish that $$A$$ (which is a $$(n+1) \times (n+1)$$ matrix) has eigenvalue $$1$$ with order of multiplicity at least $$n-1$$.

Consider hyperplane $$x^{\perp}$$ of $$\mathbb{R}^n$$ defined as the set of vectors $$y$$ that are orthogonal to $$x$$. Let $$(y_1,y_2,\cdots y_{n-1})$$ be a basis of $$x^{\perp}$$ ; then,

$$\underbrace{\begin{pmatrix} I_n & x \\ x^T & 1 \end{pmatrix}}_{A}\underbrace{\begin{pmatrix} y_k\\ 0 \end{pmatrix}}_{V_k}=1\underbrace{\begin{pmatrix} y_k\\ 0 \end{pmatrix}}_{V_k} \ \ \ \text{for} \ \ k=1,2, \cdots (n-1),$$

proving that $$V_k$$ is an eigenvector associated with eigenvalue $$1$$.

Due to the fact that trace$$(A)=n+1$$, the two remaining eigenvalues are of the form $$\alpha$$ and $$\beta:=2-\alpha$$. We can assume, WLOG that $$\alpha \leq 1 \leq \beta$$.

Besides, using the so-called Schur determinant identity (Eigenvalues of a Block Matrix from Schur Determinant Identity) for the computation of the determinant of a $$2 \times 2$$ block matrix, we obtain :

$$\det(A)=1-x^Tx$$

As the determinant is also the product of eigenvalues, we get the following identity :

$$\det(A)=1-\|x\|^2=\alpha(2-\alpha)\tag{1}$$

Thus, one can compute explicitly the two remaining eigenvalues by solving quadratic equation (1), with the following explicit solutions (if we assume that $$\alpha$$ is the smallest eigenvalue)

$$\alpha=1 - \|x\| \ \ \ \implies \ \ \ \beta:=2-\alpha=1 + \|x\|\tag{2}$$

As the criteria for a symmetric matrix do be semi-definite positive is that must have all eigenvalues $$\geq 0$$, this criteria becomes $$\alpha \geq 0$$, i.e., $$\|x\| \leq 0$$. $$\square$$

Remark : eigenvalues $$\alpha$$ and $$\beta$$ can be associated with eigenvectors $$\begin{pmatrix} x\\ -\|x\| \end{pmatrix}$$ and $$\begin{pmatrix} x\\ \|x\| \end{pmatrix}$$ resp.

Let us take an example in the case $$n=4$$ ; let $$m=1/n$$ ; consider matrix :

$$A:=\left(\begin{array}{rrrr|r} 1 & & & & m \\ & 1 & & & m \\ & & 1 & & m\\ & & & 1 & m\\ \hline m & m & m & m & 1 \\ \end{array}\right)$$

One can check, using (2), that the spectrum of $$A$$ is

$$(\tfrac12, 1 , 1, 1, 1, \tfrac32).$$

Just now, I "googled" with keywords "bordered identity matrix" : I found in (Eigenvalues of a certain bordered identity matrix) a somewhat similar computation that I did in the Appendix.

• Thank you for your answer! My main purpose was showing $||x||_2 \leq 1$ holds iff the matrices I gave are Psd. I proved one by Schur complement theory on PSD matrics, but for the equivalence I just followed the definition of PSD and by contradiction showed that if one holds, the other one should hold etc.. – independentvariable Mar 23 at 19:28
• But yours seem the better way, not the 'dirty' $a^T X a \geq 0$ for all $a$ approach... I don't like it, it seems too manual – independentvariable Mar 23 at 19:35