Positive semidefiniteness of a block matrix

Question

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))$?

Answer 1

Claim: $M$ is positive semi-definite.

To realize this, look at the question number $3.2$ from chapter $3$ of the following book by Dr. Vern Paulsen :

https://books.google.ca/books/about/Completely_Bounded_Maps_and_Operator_Alg.html?id=VtSFHDABxMIC&hl=en

For quick reference, let me write the question: Suppose $P,Q,S$ are operators on some Hilbert space $\mathcal{H}$ with $P,Q$ positive semi-definite, then the matrix $$ \begin{bmatrix} P & S\\ S^* & Q \end{bmatrix} $$ will be positive semi-definite if and only if $|\langle{Sx},{y}\rangle|^2\leq \langle{Py},{y}\rangle \langle{Qx},{x}\rangle$ for every $x,y\in \mathcal{H}$.

Notice that in your question $P=Q=I+A$ which is psd and $S=S^*=-I$. Use Cauchy-Schwartz inequality to deduce that $|\langle{-x},{y}\rangle|^2\leq \langle{(I+A)y},{y}\rangle \langle{(I+A)x},{x}\rangle$ for every $x,y\in \mathbb{C}^n$. This proves the claim.

Answer 2

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.

Answer 3

You can actually get the eigenvalues of your matrix in terms of the eigenvalues of $A$, by directly solving the linear system for them.

To see this, note that the eigenvalue eigenvector pairs are solutions to the system, $$ \begin{bmatrix} I + A - \lambda I & -I \\ -I & I + A - \lambda I \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}. $$ Doing one step of block Gaussian elimination to solve the system yields, $$ \begin{bmatrix} I + A - \lambda I & -I \\ 0 & I + A - \lambda I - (I + A - \lambda I)^{-1} \end{bmatrix} \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}. $$ In particular, the second equation that must be satisfied is, $$\left(I + A - \lambda I - (I + A - \lambda I)^{-1}\right)y=0,$$ or $$\left((I + A - \lambda I)^2-I\right)y = 0.$$ Since everything here is either an identity matrix or $A$, the solutions to this system are the eigenvectors of $A$. Furthermore, given an eigenvalue $a$ of $A$, the eigenvalues of this system must be solutions to the quadratic equation, $$(1 + a - \lambda)^2 -1 = 0$$ which are $\lambda = a$ and $\lambda = a+2$.