In an effort to broaden my blog readership, today’s topic is generating random unimodular matrices with a column of ones. Here’s the tweet from a fellow Hawkeye that got me thinking about this:
Possible to generate “random” totally unimodular matrices with at least one column of all ones? My simplex-pivoting students will thank you!
— Sam Burer (@sburer) September 11, 2013
A unimodular matrix is a matrix whose determinant is +/-1, denoted det(M) for a matrix M. Two important facts are that det(A)det(B)=det(AB), and the determinant of a triangular matrix is the product of the diagonal entries.
So randomly generating a unimodular matrix is easy:
- Generate a lower triangular matrix L and upper triangular matrix U with 1s on the diagonal and random entries elsewhere.
- The problem is that the product M=LU does not have a column of ones. But we can fix this. Let’s assume that we want the last column of M should contain all 1s. Then the inner product of row I of L and the last column of U should be 1. We can fiddle with the last element of U in this inner product so that this works out: changing this element will not change the determinant. There is a special case for the lower right element because we do not want to change the diagonals, so in that case we should adjust L instead.
Here is the code in python, assuming the NumPy package has been loaded. I do not use “dot” to compute val so I don’t have to special case i=0. Too long for a tweet, and matrices that are produced are a little funny looking, and if we get unlucky we may divide but zero, but good enough for a blog post.
def rand_unimod(n): l = tril(random.randint(-10, 10, size=(n,n))).astype('float') u = triu(random.randint(-10, 10, size=(n,n))).astype('float') for i in range(0, n): l[i, i] = u[i, i] = 1.0 if i < n - 1: val = sum([l[i, j] * u[j, n-1] for j in range(0, i)]) u[i, n-1] = (1 - val) / l[i, i] else: val = sum([l[i, j] * u[j, n-1] for j in range(1, i+1)]) l[n-1, 0] = (1 - val) / u[0, n-1] return dot(l, u), l, u
4 thoughts on “Generating random unimodular matrices with a column of ones”
Yes! Post to be updated over the weekend…
I have a formula to share. Suppose that the 1st column contains all 1’s. Then the matrix can be expressed as
[ 1 x^T ]
[ ——————– ]
[ e ex^T + B ]
where e is a vector of all 1’s, x is a random vector of integers, and B is a random unimodular matrix.
Oops! it’s not TUM for the formula. It’s interesting.