Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider the following probability measure on the integers concentrated around $0$: the probability of drawing $0$ is $\frac{1}{2}$, of drawing ($1$ or $-1$) is $\frac{1}{4}$ split evenly among the two choices, of drawing ($2$ or $-2$) is $\frac{1}{8}$ and so forth. Call this measure $\mu$.

Now consider an $n \times n$ matrix $M$ whose entries have been drawn in a $\mu$-iid fashion. Define a $\mu$-random row operation on $M$ as follows: pick two numbers $p,q$ randomly according to the uniform distribution on $\lbrace 1,2,\ldots,n \rbrace$ and also pick an integer $m$ according to $\mu$. Then, we perform the row operation that replaces the $p$-th row of $M$ by itself plus $m$ times the $q$-th row. Similarly define a $\mu$-random column operation.

What does the distribution of entries in $M$ look like as the number of $\mu$-random row and column operations goes to $\infty$?

Background

I should confess that this question does not arise from my own research, but rather from watching the progress of some undergraduates taking linear algebra who have not quite mastered the Gaussian elimination algorithm yet. Their strategy for row reduction seemed to involve blindly performing row operations without caring for pivots or GCD's or anything of the sort. In order to incur a minimal computational burden, they seemed to prefer small scalar multiples of rows, so I chose $\mu$ to be concentrated on the small integers. What are the odds that they will get lucky with this blind strategy and end up with a matrix largely populated with zeros?

share|improve this question
3  
I can't think of a better motivation for that problem. –  Emilio Pisanty Dec 2 '12 at 0:30
add comment

2 Answers

I would also mention a paper by H. Furstenberg and H. Kesten, "Products of random matrices", 1960.

In fact, a general idea is that when you are making a product of random matrices, unless there is a degeneracy (an invariant finite union of planes), almost surely you will see the rows to become more and more aligned (that is, the projectivization of your dynamics collapses almost all the projective space, including the points corresponding to the base vectors $e_i$, to one "wandering" point).

And quite naturally it means, that if the matrices are in the $SL(n,\mathbb{R})$ group, the contraction in all the directions but one means expansion in the last one: the elements of the product grow exponentially.

Now you multiply your matrix M on both sides by such matrices. It seems rather clear (though, perhaps, you need some cleanup for it to become a really formal proof) that what you will have is still a matrix with exponentially big entries, almost-aligned (angle close to zero) rows and almost-aligned columns.

Poor students! If they don't hit the answer quickly, they wander off to infinity in $SL(n,\mathbb{Z})$...

share|improve this answer
add comment

You are taking a random product of transvections corresponding to row and column operations, and then multiplying your initial matrix $M$ by this product. Obviously, $M$ is a bit of a red herring, it is the random product you care about, and this has been studied extensively. The canonical reference is:

Bougerol, Philippe, and Jean Lacroix. Products of random matrices with applications to Schrödinger operators. Birkhäuser, 1985.

share|improve this answer
    
Thanks for the book reference, Igor, but which part contains an answer to this question? –  Vidit Nanda Dec 2 '12 at 1:58
    
Look at the central limit theorems (page 121, e.g.) It will take a little while to unravel the notation :) –  Igor Rivin Dec 2 '12 at 4:47
add comment

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.