Prove that KKT matrix has at least n-m positive and m negative eigenvalues. I would like to prove that KTT matrix defined below has at least n-m positive and at least m negative eigenvalues. I also wonder if we can say that null(H) spans the same vectors as null(A) since it is on the null(A)? What is the intuitive meaning of being on the nullspace of a matrix? Any hints would be appreciated! Thanks!
$
   K:=
  \left[ {\begin{array}{cc}
   H & A^{T} \\
   A & 0 \\
  \end{array} } \right]
$  
$ H \in R^{n\times{}n}$ symmetric, $ A \in R^{m\times{}n}$ full rank, rank(A) = m
Assume H is positive definite , $x^{T}Hx >0 $ on the nullspace of A , $Ax =0$ where $ x\neq0 $
 A: This question is equivalent to exercise $10.1$ of the book Convex Optimization by Stephen Boyd and Lieven Vandenberghe.
The answer can be found in this pdf, which contains the solutions of homework 8 from Prof. Boyd's EE364a-Convex Optimization I course.
Edit: The answer to question 10.1 of the book is transcribed bellow, in case the course website is taken down.
10.1 - Solution
(a)


*

*Conditions 1 and 2. If $x \in \mathcal{N}(A) ∩ \mathcal{N}(P)$, $x \neq 0$, then $Ax = 0, x \neq 0$, but $x^TP x = 0$, contradicting the second statement. Conversely, suppose the second statement fails to hold, i.e., there is an $x$ with $Ax = 0$, $x \neq 0$, but $x^TP x = 0$. Since $P \geq 0$, we conclude $P x = 0$, i.e., $x ∈ \mathcal{N}(P)$, which contradicts the first statement.

*Conditions 2 and 3. If $Ax = 0$, $x \neq 0$, then $x$ must have the form $x = F z$, where $z \neq 0$ because $\mathbf{rank}(F) = n−p$. Then we have $x^TP x = z^TF^TP F z > 0$.

*Conditons 2 and 4. If the second condition holds then
$$
x^T(P + A^TA)x = x^TP x + \| A^T x \|^2_2 > 0$$
for all nonzero $x$, so the last statement holds with $Q = I$. If the last statement holds for some $Q \geq 0$ then $$
x^T(P + A^TQA)x = x^TP x + x^TA^TQAx > 0$$
for all nonzero $x$. Therefore if $Ax = 0$ and $x \neq 0$, we must have $x^TP x > 0$.


Now let us show that the four statements are equivalent to nonsingularity of the KKT matrix. First suppose that $x$ satisfies $Ax = 0$, $P x = 0$, and $x \neq 0$. Then
$$\left[
\begin{array}{cc}
P & A^T \\
A & 0
\end{array}
\right]
\left[
\begin{array}{cc}
x \\
0
\end{array}
\right]=0,$$
which shows that the KKT matrix is singular.
Now suppose the KKT matrix is singular, i.e., there are $x$, $z$, not both zero, such that
$$\left[
\begin{array}{cc}
P & A^T \\
A & 0
\end{array}
\right]
\left[
\begin{array}{cc}
x \\
z
\end{array}
\right]=0.$$
This means that $P x + A^Tz = 0$ and $Ax = 0$, so multiplying the first equation on the left by $x^T$, we find $x^TP x + x^TA^Tz = 0$. Using $Ax = 0$, this reduces to $x^TP x = 0$, so we have $P x = 0$ (using $P \geq 0$). This contradicts (a), unless $x = 0$. In this case, we must have $z \neq 0$. But then $A^Tz = 0$ contradicts $\mathbf{rank} (A) = p$.
(b)
From part (a), $P + A^TA > 0$. Therefore there exists a nonsingular matrix $R \in \mathbf{R}^{n \times n}$ such that$$
R^T(P + A^TA)R = I.$$
Let $AR = UΣV^T_1$ be the singular value decomposition of $AR$, with $U \in \mathbf{R}^{p \times p}$, $\Sigma = \mathbf{diag}(σ_1, . . . , σ_p) \in \mathbf{R}^{p \times p}$ and $V_1 \in \mathbf{R}^{n \times p}$. Let $V_2 \in \mathbf{R}^{n \times (n-p)}$ be such that $$
V = [V_1 V_2]$$
is orthogonal, and define $$
S =[Σ \ 0 ] \in \mathbf{R}^{p \times n}.$$
We have $AR = USV^T$, so $$
V^TR^T(P + A^TA)RV = V^TR^TP RV + S^T S = I.$$
Therefore $V^TR^TP RV = I − S^T S$ is diagonal. We denote this matrix by Λ: $$
Λ = V^TR^TP RV = \mathbf{diag}(1 − σ^2_1, \dots, 1 − σ^2_p, 1, \dots , 1).$$
Applying a congruence transformation to the KKT matrix gives
$$
\left[
\begin{array}{cc}
V^TR^T & 0 \\
0 & U^T
\end{array}
\right]
\left[
\begin{array}{cc}
P & A^T \\
A & 0
\end{array}
\right]
\left[
\begin{array}{cc}
RV & 0 \\
0 & U
\end{array}
\right] = 
\left[
\begin{array}{cc}
\Lambda & S^T \\
S & 0
\end{array}
\right]
,$$
and the inertia of the KKT matrix is equal to the inertia of the matrix on the right.
Applying a permutation to the matrix on the right gives a block diagonal matrix with $n$ diagonal blocks
$$
\left[
\begin{array}{cc}
\lambda_i & \sigma_i \\
\sigma_i & 0
\end{array}
\right]
, \quad i = 1, \dots , p, \quad λ_i = 1, \quad i = p + 1, \dots , n.
$$
The eigenvalues of the $2 \times 2$-blocks are
$$
\frac{\lambda_i \pm \sqrt{\lambda^2_i + 4 \sigma^2_i }}{2} 
$$
i.e., one eigenvalue is positive and one is negative. We conclude that there are $p + (n − p) = n$ positive eigenvalues and $p$ negative eigenvalues.
