Positive semidefiniteness of a block matrix 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))$?
 A: 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.
A: 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.
A: 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$.
