7

Assume $$C=\sum_{i=1}^nA_iP_i$$ where each $P_i$ is an $n\times n$ orthogonal projection matrix ($P_i=P_i^\top$ and $P_i=P^2_i$) and $A_i$ is an $n\times n$ matrix of zero elements except the $(i,i)$-th element equal to one.

Can I say something about the eigenvalues of $C$?

glS
  • 6,818
user293017
  • 197

1 Answers1

3

The matrix $A_iP_i$, is a matrix containing a lot of zeros, and its $i$-th row is equal to the $i$-th row of $P_i$. That is, the resulting matrix has rows all with Euclidean norm equal to $1$. This implies $\|C\|_2 \le \sqrt n$: $$ \|Cx\|_2^2 =\sum_i (c_i^Tx)^2\le \sum_i \|c_i\|^2 \|x\|^2 = n \|x\|^2, $$ where $c_i$ is the $i$-th row of $C$. This bound is realized if all rows of $C$ are the same up to factors with absolute value $1$.

This shows that all eigenvalues of $C$ are in the circle $\{z\in \mathbb C:\ |z|\le \sqrt n\}$. This bound is sharp as the matrix $C=(c_{ij})$ with $c_{ij}=\frac1{\sqrt n}$ shows.

Using Gershgorin theorem, one can prove inclusions for eigenvalues. The radius of the Gershgorin circle $i$ can be estimated by $$ \sum_{j\ne i} |c_{ij}| \le \sqrt{n-1} \left(\sum_{j\ne i} |c_{ij}|^2 \right)^{1/2} = \sqrt{(n-1)(1-|c_{ii}|^2)}. $$ Then the eigenvalues of $C$ are inside the circles with center $c_{ii}$ and radius as above. If more is known about the entries of $C$, the bound can be improved.

daw
  • 49,113
  • 2
  • 38
  • 76
  • Thank you for your response. I'm confused in the notations. In the first part of the answer: what did you mean by the matrix $A$. Furthermore, I did not understand how the bound on the radius of the Gershgorin circle is established. – user293017 Nov 24 '15 at 17:28
  • @user293017 I confused $A$ and $C$. Gershgorin bound: first inequality is $l^1$-norm against $l^2$-norm, second equality uses that $\sum_{j}|c_{ij}|^2=1$. – daw Nov 24 '15 at 18:37
  • You are right! Sorry for the confusion, I thought $A_i$ had a row of ones. – dafinguzman Nov 25 '15 at 10:42