Results 1 to 3 of 3

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

  1. #1
    Newbie
    Joined
    Aug 2011
    Posts
    2

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

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7

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

    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.
    Last edited by Opalg; August 14th 2011 at 11:55 AM. Reason: pointing out basic mistake
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2011
    Posts
    2

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

    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...
    Last edited by Polynomial; August 16th 2011 at 05:17 PM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: July 13th 2011, 01:54 AM
  2. Spectral Radius
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 9th 2011, 11:10 PM
  3. Spectral radius of sum of commuting matrices
    Posted in the Advanced Algebra Forum
    Replies: 5
    Last Post: July 3rd 2010, 08:47 PM
  4. spectral radius question
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: April 9th 2010, 09:38 AM
  5. Spectral Radius
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 11th 2008, 12:45 PM

Search Tags


/mathhelpforum @mathhelpforum