5
$\begingroup$

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!

Improve this question
$\endgroup$
5
  • 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
    Commented Sep 4, 2018 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
    Commented Sep 4, 2018 at 1:55
  • $\begingroup$ presumably of interest: Perron–Frobenius theorem. $\endgroup$
    – AccidentalFourierTransform
    Commented Sep 4, 2018 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
    Commented Sep 4, 2018 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
    Commented Sep 4, 2018 at 2:37

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Great! $\frac{4n^2}{\pi^2}$ is precisely $0.4n^2$. Appreciate that! $\endgroup$
    – dave2d
    Commented Sep 4, 2018 at 3:22

You must log in to answer this question.

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