Why can't Mathematica compute the null space of these matrices?

Question

I'm writing a library of functions to work with musical pitch-class vectors. One of my functions gives me a skew-symmetric matrix modulo 12 that corresponds to the differences between components of the pitch-class vector. A sample input and output would look like this:

In[1] := IntervalDifferenceMatrix[set_] := 
          Module[{set1, len}, set1 = Flatten[set]; len = Length[set1]; 
          Table[Mod[set1[[j]] - set1[[i]], 12], {i, 1, len}, {j, 1, len}]]
In[2] := IntervalDifferenceMatrix[{{0}, {1}, {4}}]
Out[2] = {{0, 1, 4}, {11, 0, 3}, {8, 9, 0}}

So, let's say that I then want to find the null space of these matrices modulo 12. Mathematica can handle some of them fine...

In[3] := IntervalDifferenceMatrixNullSpace[matrix_] := 
          Module[{len, null}, null = NullSpace[matrix, Modulus -> 12]; 
          len = Length[null]; 
          Table[Transpose[{Flatten[null[[i]]]}], {i, 1, len}]]
In[4] := IntervalDifferenceMatrixNullSpace[{{0, 1, 4}, {11, 0, 3}, {8, 9, 0}}]
Out[4] = {{{3}, {8}, {1}}}
In[5] := IntervalDifferenceMatrixNullSpace[IntervalDifferenceMatrix[{{0}, {1}, {4}, {7}, {11}}]]
Out[5] = {{{10}, {1}, {0}, {0}, {1}}, {{6}, {5}, {0}, {1}, {0}}, {{3}, {8}, {1}, {0}, {0}}}

But for whatever reason, it's failing on a select few matrices. For example,

In[6] := IntervalDifferenceMatrixNullSpace[IntervalDifferenceMatrix[{{0}, {2}, {4}, {7}, {11}}]]

gives me an error in performing RowReduce[] on the interval difference matrix, saying

{{10,0,2,5,9},{0,2,4,7,11},{0,0,0,0,0},{0,0,0,0,0},{0,0,0,0,0}} is not valid modulo 12.

However, I know that the null space can't be empty, as any interval difference matrix has a vanishing determinant modulo 12. If I do

Solve[IntervalDifferenceMatrix[{{0}, {2}, {4}, {7}, {11}}].{{a}, {b}, {c}, {d}, {e}} == {{0}, {0}, {0}, {0}, {0}}, Modulus -> 12]

...then I get the space of solutions that I'm looking for. Does anybody know why NullSpace[] is failing, and how I can fix my code?

Answer 1

In addition to using Solve one can augment the matrix by a row containing the modulus in each position and use HermiteDecomposition. Any zero row (modulo the modulus) in the resulting HNF corresponds to a null vector in the conversion matrix.

i1 = IntervalDifferenceMatrix[{{0}, {1}, {4}}];
i2 = Append[i1, ConstantArray[12, 3]];
{uu, hnf} = HermiteDecomposition[i2]

(* Out[22]= {{{-72, -9, -28, 27}, {1, 0, 0, 0}, {-63, -8, -25, 
   24}, {-96, -12, -36, 35}}, {{1, 0, 9}, {0, 1, 4}, {0, 0, 12}, {0, 
   0, 0}}} *)

Quick check:

In[28]:= uu.i2 == hnf

(* Out[28]= True *)

Since hnf[[3]] is a zero row, uu[[3]] corresponds to a null vector. Now snip the last element since it's the one that's multiplying the modulus to get those zeros. Note that uu[[4]] does not work because it is all zeros modulo 12.

Most[uu[[3]]]

(* Out[33]= {-63, -8, -25} *)

Check:

In[35]:= Mod[Most[uu[[3]]].i1, 12]

(* Out[35]= {0, 0, 0} *)

Here is the properly reduced null vector.

Mod[Most[uu[[3]]], 12]

(* Out[37]= {9, 4, 11} *)