Consider the following block matrix
$$M =
\begin{bmatrix}
I+A & -I\\ -I & I+A
\end{bmatrix}$$
in which $I$ represents the identity matrix of size $n$ and $A$ is a symmetric and positive semidefinite (PSD) matrix. Can I say $M$ is PSD?
Since $I+A$ is positive definite, I can apply the determinant formula for block-matrices which gives $1 + \mbox{eig}(A)$ as eigenvalues of $M$. What are the other eigenvalues? Are they smaller than $1 + \max(\mbox{eig}(A))$?
Best Answer
The idea is to create eigenvectors of $M$ by combining two eigenvectors of $A$ into one vector.
Let $v$ be an eigenvector of $A$ to the eigenvalue $\lambda\ge0$. Then $$ M\pmatrix{ v\\v} = \pmatrix{(1+\lambda-1)v\\ (-1+\lambda+1)v} =\lambda \pmatrix{ v\\v}. $$ In the same spirit, we obtain $$ M\pmatrix{ v\\-v} = \pmatrix{(1+\lambda+1)v\\ (-1-\lambda-1)v}=( \lambda +2)\pmatrix{ v\\-v}. $$ One can now argue, that this construction yields all eigenvalues of $M$ accompanied with a basis of eigenvectors. Hence $M$ is positive semidefinite.
The latter one can be proven quite quickly: $$ \pmatrix{v_1\\v_2}^TM\pmatrix{v_1\\v_2}=\pmatrix{v_1\\v_2}^T\pmatrix{ v_1 + Av_1-v_2 \\ -v_1 +v_2+Av_2}= v_1^Tv_1+v_1^TAv_1 - 2v_1^Tv_2+v_2^Tv_2+v_2^TAv_2 \ge v_1^TAv_1+v_2^TAv_2+(v_1-v_2)^T(v_1-v_2) \ge0. $$
This can be also obtained by noting that $$ M = I_2 \otimes A + \pmatrix{ 1& -1\\-1&1} \otimes I_n $$ with $\otimes$ being the Kronecker product. Eigenvectors of the Kronecker product of two matrices are all Kronecker products of their eigenvectors.
If $v$ is an eigenvector of $A$, then $x\otimes v$ is an eigenvector of $I_2 \otimes A$ for any $x\ne 0$. Similarly, $z\otimes y$ is an eigenvector of $ \pmatrix{ 1& -1\\-1&1} \otimes I_n$ for $z=\pmatrix{1\\ \pm1}$, $y\ne0$. This shows that $ z \otimes v $ is an eigenvector of $M$ with $z=\pmatrix{1\\ \pm1}$ and $v$ an eigenvalue of $A$. Moreover, this construction gives all eigenvalues.