How to prove the following equality regarding the maximum eigenvalue of a matrix? matrix $A\in\mathbb{R}^{m\times n}$, the following equality holds,
$\lambda_{max}\left(\begin{bmatrix}A\cdot A^T &A\\A^T & I\end{bmatrix}\right)=\lambda_{max}(A\cdot A^T)+1$, where $I$ is the identity matrix, $\lambda_{max} (\cdot)$ is the defined as the maximum eigenvalue of a matrix.
It seems like correct, but I do not know how to prove that?
 A: This answer does not assume that $A$ is square.
The following similarity transformation shows the claim
$$ \begin{bmatrix} I & 0 \\ A^T & I \end{bmatrix}\begin{bmatrix} AA^T & A \\ A^T & I \end{bmatrix}\begin{bmatrix} I & 0 \\ -A^T & I \end{bmatrix} = \begin{bmatrix} 0 & A \\ 0 & A^T A + I \end{bmatrix}.$$
A: In fact, the eigenvalues of $M=\begin{bmatrix}A\cdot A^T &A\\A^T & I\end{bmatrix}$ come in pairs, one of which is zero and the other of which is precisely $1$ more than the corresponding eigenvalue of $=A\cdot A^T$.
To show this, start by showing it for $A$ diagonal; that is pretty easy if you write the eigenvector of $M$ as 
$$
\pmatrix{x_1\\x_2\\ \vdots\\ x_n \\ y_1\\y_2\\ \vdots \\y_n }
$$
because for a given eigenvalue $d_k$ (of $A$) and an eigenvalue $\lambda_k$ (of $M$), you have 
$$
\left. \begin{array}{c}d_k^2 x_k + d_k y_k = \lambda_kx_k\\
d_k x_k +  y_k =\lambda_k y_k\end{array}\right\} \implies x_k=d_ky_k \\
d_k^3 y_k + d_k y_k = \lambda_k d_k y_k \implies \lambda_k = d_k^2+1
$$
This shows that when $A$ is diagonal the eigenvalues are as stated above or zero.
Next show that if $A = P^{-1}DP$ then $M(A)$ is just a similarity transformation acting on $M(D)$.  (Hint: The transformation matrix has blocks looking like $P$ and P^{-1}=P^T.) Thus it has the same eigenvalue spectrum; and also $AA^T$ has the same eignevalue spectrum as $D^2$.
Combining these gives the desired theorem.
A: Note that
$$
\lambda_{max}\pmatrix{AA^T & A\\A^T & I} = 
\lambda_{max}\left[\pmatrix{A\\I} \pmatrix{A\\I}^T\right] = \max_{\|x\| = 1} \left\|\pmatrix{A\\I}x\right\|^2 = \\
\max_{\|x\| = 1} \left\|\pmatrix{Ax\\x}\right\|^2 = 
\max_{\|x\| = 1} (\|Ax\|^2 + \|x\|^2) = \max_{\|x\| = 1} (\|Ax\|^2 + 1) =\\
1 + \max_{\|x\| = 1}\|Ax\|^2 = 1 + \lambda_{max}(A^TA)
$$

Alternative approach: suppose that $A$ has SVD $A = U\Sigma V^T$.  Then we have
$$
\pmatrix{AA^T & A\\A^T & I} = 
\pmatrix{U\\&V} \pmatrix{\Sigma\Sigma^T & \Sigma\\ \Sigma^T & I}
\pmatrix{U\\&V}^T
$$
So, $A$ is similar to the matrix 
$$
\pmatrix{\Sigma\Sigma^T & \Sigma\\ \Sigma^T & I}
$$
Then apply Mark's proof for the diagonal case.
