# Spectral norm of psuedoinverse of a matrix

I have a symmetric $$d\times d$$ matrix, such that all entries are either +1 or -1, therefore the diagonal entries are +1. I want to upper bound the spectral norm of the psuedoinverse of such a matrix. I did some simulations on matlab, and I find that the spectral norm of psuedoinverse is always less than or equal to 1. If this is indeed true, how do I show it, if not, what is a counterexample?

• Presumably you mean for $n >1$ as it is exactly $1$ for $n=1$. Commented Jan 26, 2020 at 20:55
• For $n=3$ the matrix of all $-1$ except $1$ on the diagonal has norm of the pseudo inverse equal to one. Commented Jan 26, 2020 at 21:05
• Sorry I meant less than or equal to 1. Commented Jan 26, 2020 at 21:43

Random counterexample: $$A=\pmatrix{ 1& 1&-1& 1& 1\\ 1& 1& 1&-1& 1\\ -1& 1& 1& 1& 1\\ 1&-1& 1& 1& 1\\ 1& 1& 1& 1& 1}.$$ The five eigenvalues of $$A$$ are $$-2,\,\frac{3-\sqrt{17}}{2},\,2,\,2$$ and $$\frac{3+\sqrt{17}}{2}$$. Since $$|\lambda|_\min(A)=\left|\frac{3-\sqrt{17}}{2}\right|\approx0.56<1$$, we have $$\|A^{-1}\|_2=\frac{1}{|\lambda|_\min(A)}>1$$.
• Nevermind, I figurred it out. $aa^\top = u\cdot \sqrt{d}\cdot \sqrt{d}\cdot u$, where u is the normalized unit vector of a, so $d$ is the only eigenvalue, hence norm of psuedoinvers = $1/d$ Commented Jan 26, 2020 at 22:13