### The Matrix

The Matrix

Here is a factoid which might be a nice exercise.

Fix integers 1 ≤

q≤p. Consider thep×pmatrix where the entry in rowiand columnjis:

- 1, if
i+jmodpis one of {0, 1, …,q-1};- 0, otherwise.
This matrix is a cyclic matrix with

qconsecutive ones diagonals; if you drew 1 as black and 0 as white, the version withp= 11 andq= 7 looks like:

Easy Exercise: prove that the determinant is zero whenpandqare not relatively prime.

Harder Exercise: prove that the determinant’s absolute value isqwhenpandqare 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 *t*^{2} columns, and two row-blocks of size *t*^{2}–*t*+1 and *t*-1; there are exactly *t* ones per row. (Pictured: *t*=4.)

Maple suggests: the determinant’s absolute value ist.^{t-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!

Filed under: diagrams, math | 1 Comment

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…)