### The Matrix

13Oct11

The Matrix

Here is a factoid which might be a nice exercise.

Fix integers 1 ≤ qp. Consider the p×p matrix where the entry in row i and column j is:

• 1, if i+j mod p is one of {0, 1, …, q-1};
• 0, otherwise.

This matrix is a cyclic matrix with q consecutive ones diagonals; if you drew 1 as black and 0 as white, the version with p = 11 and q = 7 looks like:

Easy Exercise: prove that the determinant is zero when p and q are not relatively prime.

Harder Exercise: prove that the determinant’s absolute value is q when p and q are not relatively prime.

I have an ugly proof of this. It implies an obstacle to some possible results in iterated linear programming algorithms, which is how I came across it. For a similar reason, I tried another family of matrices, which look like this:

It has t2 columns, and two row-blocks of size t2t+1 and t-1; there are exactly t ones per row. (Pictured: t=4.)

Maple suggests: the determinant’s absolute value is tt-1.

Given that the matrices are sort of weirdly structured, I am a little surprised how simple this formula is.

This shows that (1/t, 1/t, …, 1/t) is an extreme point solution for the related set cover LP. In turn, this is interesting to me since it shows that a type of extreme point lemma for iterated rounding does not extend to the priority tree cover problem, nor to a related set cover problem with strip graphs.

I posted this since I am likely to lose it if I don’t write it down in a searchable place, and by Murphy’s law it would turn out to be very useful if I lost it!