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?
On
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.
On
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}.$$
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.