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!

Advertisements


One Response to “The Matrix”

  1. 1 Anonymous

    I see why the easy exercise is simple, but then I have given up on the hard one… Anyhow, I am sure there is a simple explanation for your maple conjecture too, these things are never hard to prove. (Except for me…)


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: