2
$\begingroup$

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?

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

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.

$\endgroup$
  • 1
    $\begingroup$ 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.. $\endgroup$ – independentvariable Mar 23 at 19:28
  • 1
    $\begingroup$ 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 $\endgroup$ – independentvariable Mar 23 at 19:35

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.