Iterating Random Matrix Operations

Question

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?

Answer 1

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})$...

Answer 2

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.