Mixing
Largest Eigenvalue of a Matrix with Special Form in terms of n
Clash Royale CLAN TAG#URR8PPP
up vote
5
down vote
favorite
In one step of solving a difficult problem, I would like to know the largest eigenvalue of a matrix with this pattern:
$$A_n = beginbmatrix
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
endbmatrix$$
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_maxapprox 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!
linear-algebra matrices eigenvalues
asked Sep 4 at 1:14
dave2d
284
 |Â
show 1 more comment
up vote
5
down vote
favorite
In one step of solving a difficult problem, I would like to know the largest eigenvalue of a matrix with this pattern:
$$A_n = beginbmatrix
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
endbmatrix$$
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_maxapprox 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!
linear-algebra matrices eigenvalues
asked Sep 4 at 1:14
dave2d
284
1
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 $-2sum_k=1^n-1 k cos(2pi jk/(2n-1))$ for $0<j<n$, with $j=1$ producing the maximal root.
– Noam D. Elkies
Sep 4 at 1:50
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.
– Noam D. Elkies
Sep 4 at 1:55
presumably of interest: Perron–Frobenius theorem.
– AccidentalFourierTransform
Sep 4 at 2:07
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,...?
– Venkataramana
Sep 4 at 2:30
1
The principal minors detect the signs of the eigenvalues, not their precise sizes. For example, $bigl(1 ; 1 atop 1 ; 3bigr)$ has eigenvalues $2 pm sqrt 2$.
– Noam D. Elkies
Sep 4 at 2:37
 |Â
show 1 more comment
up vote
5
down vote
favorite
up vote
5
down vote
favorite
In one step of solving a difficult problem, I would like to know the largest eigenvalue of a matrix with this pattern:
$$A_n = beginbmatrix
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
endbmatrix$$
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_maxapprox 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!
linear-algebra matrices eigenvalues
asked Sep 4 at 1:14
dave2d
284
In one step of solving a difficult problem, I would like to know the largest eigenvalue of a matrix with this pattern:
$$A_n = beginbmatrix
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
endbmatrix$$
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_maxapprox 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!
linear-algebra matrices eigenvalues
asked Sep 4 at 1:14
dave2d
284
edited Sep 4 at 3:20
asked Sep 4 at 1:14
dave2d
284
asked Sep 4 at 1:14
dave2d
284
asked Sep 4 at 1:14
dave2d
284
284
1
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 $-2sum_k=1^n-1 k cos(2pi jk/(2n-1))$ for $0<j<n$, with $j=1$ producing the maximal root.
– Noam D. Elkies
Sep 4 at 1:50
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.
– Noam D. Elkies
Sep 4 at 1:55
presumably of interest: Perron–Frobenius theorem.
– AccidentalFourierTransform
Sep 4 at 2:07
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,...?
– Venkataramana
Sep 4 at 2:30
1
The principal minors detect the signs of the eigenvalues, not their precise sizes. For example, $bigl(1 ; 1 atop 1 ; 3bigr)$ has eigenvalues $2 pm sqrt 2$.
– Noam D. Elkies
Sep 4 at 2:37
 |Â
show 1 more comment
1
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 $-2sum_k=1^n-1 k cos(2pi jk/(2n-1))$ for $0<j<n$, with $j=1$ producing the maximal root.
– Noam D. Elkies
Sep 4 at 1:50
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.
– Noam D. Elkies
Sep 4 at 1:55
presumably of interest: Perron–Frobenius theorem.
– AccidentalFourierTransform
Sep 4 at 2:07
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,...?
– Venkataramana
Sep 4 at 2:30
1
The principal minors detect the signs of the eigenvalues, not their precise sizes. For example, $bigl(1 ; 1 atop 1 ; 3bigr)$ has eigenvalues $2 pm sqrt 2$.
– Noam D. Elkies
Sep 4 at 2:37
1
1
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 $-2sum_k=1^n-1 k cos(2pi jk/(2n-1))$ for $0<j<n$, with $j=1$ producing the maximal root.
– Noam D. Elkies
Sep 4 at 1:50
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 $-2sum_k=1^n-1 k cos(2pi jk/(2n-1))$ for $0<j<n$, with $j=1$ producing the maximal root.
– Noam D. Elkies
Sep 4 at 1:50
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.
– Noam D. Elkies
Sep 4 at 1:55
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.
– Noam D. Elkies
Sep 4 at 1:55
presumably of interest: Perron–Frobenius theorem.
– AccidentalFourierTransform
Sep 4 at 2:07
presumably of interest: Perron–Frobenius theorem.
– AccidentalFourierTransform
Sep 4 at 2:07
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,...?
– Venkataramana
Sep 4 at 2:30
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,...?
– Venkataramana
Sep 4 at 2:30
1
1
The principal minors detect the signs of the eigenvalues, not their precise sizes. For example, $bigl(1 ; 1 atop 1 ; 3bigr)$ has eigenvalues $2 pm sqrt 2$.
– Noam D. Elkies
Sep 4 at 2:37
The principal minors detect the signs of the eigenvalues, not their precise sizes. For example, $bigl(1 ; 1 atop 1 ; 3bigr)$ has eigenvalues $2 pm sqrt 2$.
– Noam D. Elkies
Sep 4 at 2:37
 |Â
show 1 more comment
1 Answer
1
active
oldest
votes
up vote
6
down vote
accepted
Your matrix has entries given by $a_ij=min(i,j)$, where $0le i,jle n-1$. Have a look at Section 3 of this paper of mine for a derivation of explicit bounds.
answered Sep 4 at 1:25
Suvrit
23.3k659119
1
Great! $frac4n^2pi^2$ is precisely $0.4n^2$. Appreciate that!
– dave2d
Sep 4 at 3:22
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
6
down vote
accepted
Your matrix has entries given by $a_ij=min(i,j)$, where $0le i,jle n-1$. Have a look at Section 3 of this paper of mine for a derivation of explicit bounds.
answered Sep 4 at 1:25
Suvrit
23.3k659119
1
Great! $frac4n^2pi^2$ is precisely $0.4n^2$. Appreciate that!
– dave2d
Sep 4 at 3:22
add a comment |Â
up vote
6
down vote
accepted
Your matrix has entries given by $a_ij=min(i,j)$, where $0le i,jle n-1$. Have a look at Section 3 of this paper of mine for a derivation of explicit bounds.
answered Sep 4 at 1:25
Suvrit
23.3k659119
1
Great! $frac4n^2pi^2$ is precisely $0.4n^2$. Appreciate that!
– dave2d
Sep 4 at 3:22
add a comment |Â
up vote
6
down vote
accepted
up vote
6
down vote
accepted
Your matrix has entries given by $a_ij=min(i,j)$, where $0le i,jle n-1$. Have a look at Section 3 of this paper of mine for a derivation of explicit bounds.
answered Sep 4 at 1:25
Suvrit
23.3k659119
Your matrix has entries given by $a_ij=min(i,j)$, where $0le i,jle n-1$. Have a look at Section 3 of this paper of mine for a derivation of explicit bounds.
answered Sep 4 at 1:25
Suvrit
23.3k659119
answered Sep 4 at 1:25
Suvrit
23.3k659119
answered Sep 4 at 1:25
Suvrit
23.3k659119
answered Sep 4 at 1:25
Suvrit
23.3k659119
23.3k659119
1
Great! $frac4n^2pi^2$ is precisely $0.4n^2$. Appreciate that!
– dave2d
Sep 4 at 3:22
add a comment |Â
1
Great! $frac4n^2pi^2$ is precisely $0.4n^2$. Appreciate that!
– dave2d
Sep 4 at 3:22
1
1
Great! $frac4n^2pi^2$ is precisely $0.4n^2$. Appreciate that!
– dave2d
Sep 4 at 3:22
Great! $frac4n^2pi^2$ is precisely $0.4n^2$. Appreciate that!
– dave2d
Sep 4 at 3:22
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmathoverflow.net%2fquestions%2f309801%2flargest-eigenvalue-of-a-matrix-with-special-form-in-terms-of-n%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
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 $-2sum_k=1^n-1 k cos(2pi jk/(2n-1))$ for $0<j<n$, with $j=1$ producing the maximal root.
– Noam D. Elkies
Sep 4 at 1:50
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.
– Noam D. Elkies
Sep 4 at 1:55
presumably of interest: Perron–Frobenius theorem.
– AccidentalFourierTransform
Sep 4 at 2:07
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,...?
– Venkataramana
Sep 4 at 2:30
1
The principal minors detect the signs of the eigenvalues, not their precise sizes. For example, $bigl(1 ; 1 atop 1 ; 3bigr)$ has eigenvalues $2 pm sqrt 2$.
– Noam D. Elkies
Sep 4 at 2:37