Spectral radius of sparse binary matrices X(n) for n-> infinity

**Polynomial** · August 13th 2011, 12:17 PM

To solve another problem, with applications in physics and mathematics, I've constructed a sequence of seemingly simple matrices X(1),X(2), ... ,X(n), defined below. For the limit n-> infinity I want to know:

the absolutely largest (real positive) eigenvalue of X(n)

I've spend a week to find a regularity in (the process of finding the) characteristic polynomials without considerable success, so I'm feeling quite frustrated and stupid now. Does anyone BTW know an official name for this kind of matrices, with two steeper-than-usual diagonal 'strings' of ones, one below and the other above the main diagonal?

The first matrices are:

X(1)=
1 0 1
1 0 0
0 1 0

X(2)=
1 0 0 0 1 0
1 0 0 0 0 0
0 1 0 0 0 0
0 1 0 0 0 0
0 0 1 0 0 1
0 0 0 1 0 0

X(3)=
1 0 0 0 0 0 0 0 1 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 1 0
0 0 0 0 0 1 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 1
0 0 0 0 0 0 0 1 0 0 0 0

X(4)=
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0

The examples above illustrate the regularity of the X(n):
$X(n):=\left( \begin{array}{cccc} A(n)& 0 & B(n) & 0 \\ 0 & I(n) & 0 & C(n) \end{array}\right)$

where

I(n) is the 2^(n-1) by 2^(n-1) unit matrix

A(n) is the 2^(n) by 2^(n-1) matrix of the form

$A(n)=\left( \begin{array}{ccccc} 1& & & & 0 \\ 1& & & & \\ & 1 & & & \\ & 1 & & & \\ & & \ldots & &\\& & & 1 & \\& & & 1 & \\& & & &1\\0& & & &1\\ \end{array}\right)$

B(n) is the 2^(n) by 2^(n-2) matrix of the form

$B(n)=\left( \begin{array}{ccccc}1& & & &0 \\0& & & & \\0& & & & \\0& & & & \\0&1 & & & \\& 0 & & & \\& 0 & & & \\& 0 & & & \\& 0 & & & \\& & \ldots & & \\& & & &1\\& & & &0\\& & & &0\\& & & &0\\0 & & & &0\\\end{array}\right)$

...and C(n) is the 2^(n-1) by 2^(n-2) matrix of the form

$C(n)=\left( \begin{array}{ccccc}1& & & &0 \\0& & & & \\0&1 & & & \\& 0 & & & \\& 0 & & & \\& & \ldots & & \\& & & &1\\& & & &0\\0 & & & &0\\ \end{array}\right)$

__________
Side remark: X(n) can also be expressed quite simply as a Khatri-Rao product.
__________

Side remark 2: Alternatively, finding the trace of (X(n))^q for very very large integers q and n would also be helpfull.
__________
Side question: what would be the best place on the internet to ask this kind of questions?
__________

Thanks in advance!

**Opalg** · August 14th 2011, 09:32 AM

One way to compute the spectral radius of a matrix $M$ is that it is the square root of the spectral radius of $M^*M$ (the star denoting the hermitian adjoint) (see correction below). If you apply that idea to the matrix $X(n)$ then you get

$X(n)^*X(n) = \begin{bmatrix}A(n)^*&0\\ 0&I(n)\\ B(n)^*&0\\ 0&C(n)\end{bmatrix} \begin{bmatrix}A(n)&0&B(n)&0\\ 0&I(n)&0&C(n)\end{bmatrix} = \begin{bmatrix}A(n)^*A(n)&0&A(n)^*B(n)&0\\ 0&I(n)&0&C(n)\\ B(n)^*A(n)&0&B(n)^*B(n)&0\\ 0&C(n)^*&0&C(n)^*C(n)\end{bmatrix}.$

This splits up as a direct sum $\begin{bmatrix}A(n)^*A(n)&A(n)^*B(n)\\ B(n)^*A(n)&B(n)^*B(n)\end{bmatrix}\bigoplus \begin{bmatrix}I(n)&C(n)\\ C(n)^*&C(n)^*C(n)\end{bmatrix}.$

If I have done the computations correctly, then each of these matrices splits up into smaller ones, and you end up with a direct sum of $2^{n-2}$ copies of each of the one- and two-dimensional matrices

$\begin{bmatrix}2&1\\1&1\end{bmatrix},\quad \begin{bmatrix}2\end{bmatrix},\quad \begin{bmatrix}1&1\\1&1\end{bmatrix},\quad \begin{bmatrix}1\end{bmatrix}.$

The largest eigenvalue in those matrices is $\tfrac12(3+\sqrt5) = \bigl(\tfrac12(1+\sqrt5)\bigr)^2.$ So it appears that the spectral radius of each of the matrices $X(n)$ is the golden ratio $\varphi = \tfrac12(1+\sqrt5).$

Edit. Serious case of brain failure: the spectral radius of $M$ is not equal to the square root of the spectral radius of $M^*M.$ That would give you the operator norm of $M.$ However, the spectral radius is dominated by the norm, so (unless I have made any other silly mistakes) the spectral radius of $X(n)$ is at most $\varphi.$

Second edit. Numerical computations with X(2) and X(3) make it look as though X(n) has just a single positive eigenvalue, which appears to be increasing towards $\varphi$ as n increases. Can't prove that though.

**Polynomial** · August 16th 2011, 09:44 AM

Hi Opalg,

Thanks for your reply. From upper and lower bounds from other techniques (not involving these matrices) I know that the first digits of the limit should be 1.503... It is not surprising that you came across the golden ratio, because the original problem involves, in some sense, a generalisation of the fibonacci numbers.

A slightly adapted version of the original problem is finding

$\kappa = \lim_{M,N \rightarrow \infty} (Y_{M,N})^{1/MN}$

where $Y_{M,N}$ is the number of binary vectors

$x=(x_{1}, x_{2}, \ldots, x_{MN})$

such that

$x_{i} x_{i+M}=0$ and $x_{i}x_{i+M-1}=0$ for all i.

It can be shown that the spectral radius of the matrices from my first post equals $\kappa$ .

I've not considered direct sums before. Maybe it's possible to come up with other matrices that can be directly attacked by your direct sum approach, without first having to multiply with the transpose...

Thread: Spectral radius of sparse binary matrices X(n) for n-> infinity

LinkBack

Thread Tools

Display

Spectral radius of sparse binary matrices X(n) for n-> infinity

Re: Spectral radius of sparse binary matrices X(n) for n-> infinity

Re: Spectral radius of sparse binary matrices X(n) for n-> infinity

Similar Math Help Forum Discussions

Regarding spectral radius of products of matrices subject to some restrictions

Spectral Radius

Spectral radius of sum of commuting matrices

spectral radius question

Spectral Radius

Search Tags