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
    Commented Jan 26, 2020 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
    Commented Jan 26, 2020 at 21:05
  • $\begingroup$ Sorry I meant less than or equal to 1. $\endgroup$ Commented Jan 26, 2020 at 21:43

1 Answer 1

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$ Commented Jan 26, 2020 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$ Commented Jan 26, 2020 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$ Commented Jan 26, 2020 at 22:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .