In one step of solving a difficult problem, I would like to know the largest eigenvalue of a matrix with this pattern: $$A_n = \begin{bmatrix} 0 & 0 & 0 & 0 &\dots & 0 \\ 0 & 1 & 1 & 1&\dots & 1 \\ 0 & 1 &2 &2 &\dots &2\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 1 & 2 & 3 & \dots& n-1 \end{bmatrix}$$

In other words, we can "peel" the "L" shaped layers from upper left corner and all layer consist of the same entry.

This matrix is symmetric, so all eigenvalues are real. It is of rank $n-1$, and numerical experiment demonstrates that it is positive semidefinite. I want to know the largest eigenvalue in terms of $n$, or have a lower bound on the largest eigenvalue in terms of $n$. I performed numerical experiment on various $n$ and it seems like we can quickly get $\lambda_{max}\approx 0.4n^2$ for large $n$. However, I don't know how to derive this result. I tried to look at the characteristic polynomial, but I could not find a pattern.

So anyone has an idea about deriving a (lower) bound on the largest eigenvalue of this matrix? Thanks!

  • 1
    $\begingroup$ Numerical experimentation suggests that this matrix [gp: matrix(n,n,i,j,min(i,j)-1) ] has characteristic polynomial $\sum_{k=0}^{n-1} (-1)^k {n-1+k \choose n-1-k} x^{n-k}$, and nonzero roots $-2\sum_{k=1}^{n-1} k \cos(2\pi jk/(2n-1))$ for $0<j<n$, with $j=1$ producing the maximal root. $\endgroup$ – Noam D. Elkies Sep 4 '18 at 1:50
  • $\begingroup$ Also, removing the row and column of zeros yields the inverse of the tridiagonal matrix with $-1$ on the two off-diagonals and $2$ in all diagonal entries except for a $1$ in the bottom right corner. $\endgroup$ – Noam D. Elkies Sep 4 '18 at 1:55
  • $\begingroup$ presumably of interest: Perron–Frobenius theorem. $\endgroup$ – AccidentalFourierTransform Sep 4 '18 at 2:07
  • $\begingroup$ I am missing something. Computing principal minors, I seem to get (after removing column and row of zeros) the numbers 1,2, 4,4,4,.... This seems to say the eigenvalues are 1,2,2,1,1,1,...? $\endgroup$ – Venkataramana Sep 4 '18 at 2:30
  • 1
    $\begingroup$ The principal minors detect the signs of the eigenvalues, not their precise sizes. For example, $\bigl({1 \; 1 \atop 1 \; 3}\bigr)$ has eigenvalues $2 \pm \sqrt 2$. $\endgroup$ – Noam D. Elkies Sep 4 '18 at 2:37

Your matrix has entries given by $a_{ij}=\min(i,j)$, where $0\le i,j\le n-1$. Have a look at Section 3 of this paper of mine for a derivation of explicit bounds.

| cite | improve this answer | |
  • 1
    $\begingroup$ Great! $\frac{4n^2}{\pi^2}$ is precisely $0.4n^2$. Appreciate that! $\endgroup$ – dave2d Sep 4 '18 at 3:22

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.