Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $M$ be an $n \times n$ matrix whose elements are random reals in [0,1]. Two questions.

  1. What is the growth rate of the magnitude of the elements of $M^k$ as a function of $k$? It is definitely exponential, but maybe the exponent is known?
  2. Is it the case that eventually one element of $M^k$ dominates, as $k \rightarrow \infty$? I have some ambiguous experimental evidence that this is the case, but because of the exponential growth, exact computation is difficult, rendering my "evidence" tenuous at best and perhaps worthless.

One can ask the same question for matrices whose elements are random reals in [-1,1], or random 0's and 1's, or random choices among $\lbrace -1, 0, 1\rbrace$, ... These question have likely been studied. Thanks for pointers and/or ideas!

share|improve this question

4 Answers 4

Powers of a matrix are more easily calculated by first diagonalizing it. Let $P, D$ be matrizes, $D$ being a diagonal matrix with $M = PDP^{-1}$, then $$M^k = PD^{k}P^{-1}.$$ The entries in D are the eigenvalues of $M$, so the entries in $M^k$ are growing exponentially with the rate of the logarithm of the largest eigenvalue of $M$, each entry being a linear combination of these eigenvalues.

So to point 2: No entry should dominate the others significantly.

This is only a partial answer.. maybe you can find something about the distribution of eigenvalues of random matrizes. =)

share|improve this answer
    
Ah! Very nice!!! But re "falling exponentially," in general it seems the largest eigenvalue is > 1. –  Joseph O'Rourke Oct 11 '10 at 15:28
    
Ehh... I'll correct that. =) –  Jens Oct 11 '10 at 15:36

The following analysis treats only the particular case of symmetric matrices $M$, which can be diagonalized by an orthogonal transformation. The key observation is that the diagonalizing matrix $P$ and the eigenvalue matrix $D$ are statistically independent. The diagonalizing matrix elements are $O(n)$ Haar distributed. Now, it is easy to see that every matrix element is a scalar product of two $O(n)$ Haar distributed n-vectors weighted by the k-th power of the eigenvalues.

At large values of k, the maximal eigenvalue dominates all eigenvalues and the contribution from the diagonalizing matrix is fixed. Thus the growth rate of all matrix elements is the natural logarithm of the maximal eigenvalue.

Moreover, the contribution of the maximal eigenvalue to the $(i,j)$ element is given by $P_{im} D_{mm}^k P_{jm}$ ($D_{mm}$ is the maximal eigenvalue). Thus the matrix element for which the product $P_{im} P_{jm}$ is maximal dominates all matrix elements of the power matrix. This element will be most likely on the diagonal because it is multiplied by the square of a Haar distributed element having a non-zero mean. The off-diagonal elements are multiplied by the product of two different Haar distributed elements thus having a zero mean.

share|improve this answer
    
I think your analysis explains what I am seeing. E.g., one random 20x20 matrix has eigenvalues 10.1, 1.8, 1.2, and smaller values. So the 10.1 eigenvalue greatly dominates when raised to the k-th power. –  Joseph O'Rourke Oct 11 '10 at 16:47
    
@Joseph: This is reminiscent of the situation with Wigner's Circular Law (for symmetric matrices) where, with a uniform distribution, one eigenvalue dominates the rest. –  whuber Oct 11 '10 at 17:08

The best results have been obtained for random matrices with Normally distributed entries, but some of them--like Wigner's Circular Law--extend to uniformly distributed entries. (Independence is crucial.) Wigner's law applies only to symmetric random matrices. Girko's Circular Law holds without the symmetry condition, but afaik requires Normally distributed entries. It says that for largish $n$ the eigenvalues are approximately uniformly distributed on a disk. For smaller $n$, before these asymptotics are reached, there is a preference for real eigenvalues extending beyond the disk. At any rate, these asymptotics will immediately give you the distribution of eigenvalues of positive integral powers of such matrices, especially when you consider that the probability all eigenvalues are distinct (and therefore the matrix is diagonalizable over $\mathbb{C}$) is one. For example, the largest eigenvalue of $M^k$ will be approximately $n^{k/2} \left( 1 - \frac{1}{2} (3 \pi / (2 n) ) ^ {2/3} \right) ^ k$.

share|improve this answer
    
Very knowledgeable answer! Incidentally, with uniform distribution in [0,1] I find that, e.g., a random 20x20 matrix has a largest eigenvalue approx. 10 consistently. –  Joseph O'Rourke Oct 11 '10 at 16:55
    
@Joseph: That's interesting. It differs from the asymptotic formula for two reasons, the first being that asymptotic conditions likely haven't been reached by n=20, the second that you're dealing with uniform entries rather than normally-distributed ones. It could be interesting to repeat your experiments with normally distributed entries. If you do this, it would be best to match moments: that is, use a normal distribution of zero mean and variance of 1/3 in comparison to a uniform on [-1,1], which also has a variance of 1/3. (Notice how the variance effectively scales all eigenvalues.) –  whuber Oct 11 '10 at 17:06

I don't have enough reputation to leave a comment, so here goes....

As other have observed, the growth rate of $M^k$ is determined by the largest eigenvalue of $M$. I just want to note that for a nonnegative matrix, the largest eigenvalue is always between the largest and smallest column sum.

That, in principle, could allow you to obtain upper and lower bounds by trying to bound how big or small the column sums usually get for the random matrix you described.

share|improve this answer
1  
Cool fact bounding the eigenvalues---Thanks! –  Joseph O'Rourke Oct 11 '10 at 19:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.