is the difference of a positive semi-definite matrix and its rank-1 approximation still positive semi-definite? suppose $M$ is a symmetric positive semi-definite matrix, its largest entry occurs along the diagonal, say, is $m_{ii}$. Then we define vector $A$ as the column containing $m_{ii}$,  i.e. (in Python language), $A=M[:,i]$, and $B=A^T/m_{ii}$.
$AB$ is a rank-1 approximation of $M$, and is also positive semi-definite. I feel the difference $M-AB$ is  positive semi-definite as well, but cannot prove it.
So my question is:  How to prove $M-AB$ is also positive semi-definite?
Thank you.
 A: This rank-1 approximation is preserved under orthogonal changes of basis.  Since $M$ is assumed symmetric, you can orthogonally diagonalize it and then the rank-1 approximation is just the matrix with a single nonzero entry, namely the largest diagonal coefficient. Replacing it by zero clearly leaves a positive semidefinite matrix.
A: $m_{ii}$ doesn't need to be the largest diagonal entry. Any nonzero diagonal entry will do. More specifically, suppose without loss of generality that $i=1$ and $m_{11}>0$. Partition $M$ as $\pmatrix{m_{11}&u^\top\\ u&H}$. Then your "$M-AB$" is equal to
$$
M-\frac{1}{m_{11}}\pmatrix{m_{11}\\ u}\pmatrix{m_{11}&u^\top}
=\pmatrix{0&0\\ 0&H-\tfrac{1}{m_{11}}uu^\top}.
$$
It is positive semidefinite if and only if $H-\tfrac{1}{m_{11}}uu^\top$ is positive semidefinite. The matrix $H-\tfrac{1}{m_{11}}uu^\top$ is known as the Schur complement of $m_{11}$ in $M$. We have
$$
\underbrace{\pmatrix{m_{11}&u^\top\\ u&H}}_M=
\underbrace{\pmatrix{1&0\\ \tfrac{1}{m_{11}}u&I_{n-1}}}_{P^\top}
\ \ \underbrace{\pmatrix{m_{11}&0\\ 0&H-\tfrac{1}{m_{11}}uu^\top}}_C
\ \ \underbrace{\pmatrix{1&\tfrac{1}{m_{11}}u^\top\\ 0&I_{n-1}}}_P.
$$
Since $M$ is positive semidefinite and $P$ is invertible, $C$ and its trailing principal submatrix $H-\tfrac{1}{m_{11}}uu^\top$ are positive semidefinite too. You can actually say more if you know Sylvester's law of inertia.
