3
$\begingroup$

I am working on a set of matrices for a project, studying their highest eigenvalue, let's call it $\lambda_{1}$.

I was curious and plotted the norm 1 of the matrix, ie $ \frac{1}{n^{2}}\sum_{i,j} |a_{i,j}|$.

I observed a similar comportement for these quantities, is there any explanation ? Is this due to the structure of my matrices ? Is there a general results ?

Thanks in advance

More information about my matrix: It's a correlation matrix, symetric and positive. The first eigenvalues is approximately $10$ times bigger than the others.

I also forgot an important thing: all variables are normalized. (and also the norm 1)

enter image description here

$\lambda1$ in red, the norm 1 in green.

$\endgroup$
3
  • $\begingroup$ Do you mean the highest eigenvalue in absolute value? $\endgroup$ Mar 28, 2013 at 14:53
  • $\begingroup$ My matrices are symetric positive, so yes $\endgroup$ Mar 28, 2013 at 14:56
  • 1
    $\begingroup$ Hah, that's a big piece of the puzzle to leave out :) $\endgroup$ Mar 28, 2013 at 14:57

2 Answers 2

3
$\begingroup$

Edit: It is unsurprising that the spectral radius $\rho(A)$ and the $\ell_1$-norm of $A$ have roughly the same trends. Since $A$ is positive definite, we have $\rho(A)=\|A\|_2$. As all norms on a finite dimensional vector space are equivalent, we would expect $\rho(A)$ to be large when the $\ell_1$-norm of $A$ is large, and vice versa.

What is surprising, though, is that $\rho(A)$ and the normalized $\ell_1$-norm of $A$ have roughly the same magnitudes. By spectral decomposition, $A=\sum_j \lambda_j \mathbf{v}_j\mathbf{v}_j^T$, where each $\mathbf{v}_j$ is a unit eigenvector of $A$ corresponding to the eigenvalue $\lambda_j$, with $\lambda_1\ge\lambda_2\ge\cdots\ge\lambda_n$. Now:

  • If $\lambda_1=\cdots=\lambda_n$, i.e. $A=\lambda_1I$, we have $\frac1{n^2}\sum_{i,j}|a_{ij}|=\frac{\lambda_1}n$.
  • If $\lambda_2,\ldots,\lambda_n\ll\lambda_1$, then $A\approx\lambda_1 \mathbf{v}_1\mathbf{v}_1^T$ and $$ \frac1{n^2}\sum_{i,j}|a_{ij}|=\frac1{n^2}\mathbf{1}^T|A|\mathbf{1} \approx\frac{\lambda_1}{n^2}\langle \mathbf{1},|\mathbf{v}|\rangle^2. $$ Yet, by Cauchy-Schwarz inequaltiy, $\langle \mathbf{1},|\mathbf{v}_1|\rangle^2\le\|\mathbf{1}\|^2\ \|(|\mathbf{v}_1|)\|^2=n$. Therefore we would expect the order of magnitude of $\frac1{n^2}\sum_{i,j}|a_{ij}|$ to be not far greater than $\frac{\lambda_1}n$.

Now you say that $\lambda_1$ is roughly ten times the other eigenvalues. While $\lambda_2,\ldots,\lambda_n$ are an order of magnitude smaller than $\lambda_1$, since there are $O(n)$ of them, they collectively may be non-negligible. However, based on the above two example cases, I would expect the order of magnitude of $\frac1{n^2}\sum_{i,j}|a_{ij}|$ to be $\frac{\lambda_1}n$ rather than $\lambda_1$. So, your findings are quite unexpected. Perhaps you may repeat the same numerical experiment for larger-sized $A$, and see if $\rho(A)$ and the normalized $\ell_1$ norm still have roughly the same magnitude. If they do, there is a good chance that there's really something interesting in it; if they don't, then your current findings are perhaps mere coincidence.

$\endgroup$
1
  • $\begingroup$ I have added the comportement wich I am talking about. $\endgroup$ Mar 29, 2013 at 15:36
2
$\begingroup$

It is surely cause of the structure of your matrix. Only for $1\times 1$ matrices is it true in general.

Take any upper triangular matrix, you can chose the values on the upper triangular matrix as large as you like still all eigenvalues will be $0$.

If you like more complicated counterexamples, take $u,v\in \mathbb{R}^n$ and study the matrix $B=u\cdot v^T$ with $u\neq 0$ and $ v\bot u$. Here all eigenvalues are $0$, and the $\infty$ norm of $B$ is the $\infty$ norm of $u$ times the 1 norm of $v$.

For symmetric positiv definit matrices the largest eigenvalue can't be bigger than the $1$ norm, as the trace is invariant under basistransformation and as diagonal form there are only positive values in the diagonal (as your matrix is positiv definit).

$\endgroup$
7
  • $\begingroup$ It's not clear by "comportement" he means that they are equal, especially since he uses the word "similar." $\endgroup$ Mar 28, 2013 at 14:54
  • $\begingroup$ @ThomasAndrews as i unterstood the question, he tries to say that when your matrix norms get bigger, your eigenvalues doe the same, and I gave him some counter example for that $\endgroup$ Mar 28, 2013 at 14:55
  • $\begingroup$ they'are not equals... I was not asking for counter exemple, but more for condition under which these quantities are "equals". I thinks the conditions for perfect equalities could help to understand the "similar" comportement. $\endgroup$ Mar 28, 2013 at 15:01
  • $\begingroup$ Oh, that's definitely true, but there still might be a strong correlation, in a statistical sense, between the two. Basically, if you pick a random matrix with $L_1$ norm in $[0,N]$, how strong would the correlation between these two values be? The upper triangular matrices are a zero-measure set of matrices, after all. However, his comment above that his matrices are symmetric positive seems to be a big part of the key. $\endgroup$ Mar 28, 2013 at 15:01
  • $\begingroup$ @ThomasAndrews and they are correlation matrices so i guess they will be strictly diagonal dominant in most cases or ? $\endgroup$ Mar 28, 2013 at 15:09

You must log in to answer this question.

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