1
$\begingroup$

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?

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

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$.

$\endgroup$
3
  • $\begingroup$ Thank you for your answer. A followup, is there an upper bound on spectral in terms of d for such matrices? $\endgroup$ Jan 26 '20 at 21:37
  • $\begingroup$ Sorry for bothering, but I realize that my question was more general than my simulation - I generate a vector of d dimensions, containing +1 or -1, then take outer product with itself. I then take the spectral norm of psuedoinverse. In my case, the rank of the matrix is 1, so the counterexample does not fit. Can I guarantee spectral norm less than or equal to 1 in this modified case? $\endgroup$ Jan 26 '20 at 22:04
  • $\begingroup$ 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$ $\endgroup$ Jan 26 '20 at 22:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.