# Method for optimal de-composition of rank-deficient integer matrices

I'm working with (integer) matrices of reduced rank and try to find a method to decompose the "redundant" columns by some base.

For instance the following matrix $A_5$

  |   1    14    24    45    46    26   24 |
| -15   -75  -130  -180  -165  -105  -50 |
A=|  50   145   230   275   215   130   35 |
| -60  -120  -170  -180  -120   -60  -10 |
|  24    36    46    40    24     9    1 |


has rank 4 and so three of the columns can be expressed by linear composition of 4. For instance

 |   1    14    24    45 |        |   46    26   24 |
| -15   -75  -130  -180 |        | -165  -105  -50 |
|  50   145   230   275 | * T =  |  215   130   35 |
| -60  -120  -170  -180 |        | -120   -60  -10 |
+ ----------------------+        +-----------------+
|  24    36    46    40 |        |   24     9    1 |


where the 4x3-matrix T can be computed by inversion of the topleft 4x4 submatrix on the lhs and premultiplication with the top 4x3 submatrix on the rhs. For instance with the shown ansatz I find a solution for $T$ - where also the entries can be made integer by multiplication with their common denominator.
For instance I got for this

|  23716    18095    24717 |
| -38192   -35035   -32109 |
|  11088    13860     3696 |  = T * ( 2^2 * 3 * 5 * 7* 11)
|  10164     5775     9933 |


Of course T differs depending on which columns I use for the lhs and which on the rhs, and an optimal T were one whose entries show such a recognizable pattern, that I can extrapolate for the cases $A_6$, $A_7,...$ which have more rows and columns but similar structures - well, that's perhaps too much for the beginning. Let's first try to just find the combination with the smallest common denominator and having small integer entries - and an algorithm for finding this.

So what I'm finally looking for is a method , an algorithm how to solve such a problem systematically. In Pari/GP there is the lindep function available which somehow employs the LLL - algorithm (if I got things correct). But that lindep works only with scalars, not with column-vectors.

Q: Is there some method to search for (hopefully: optimal) decomposition in such situations of rectangular, rankdeficient integer matrices?

Some background: the matrices $A_k$ occur in the iteration of the decremented exponential-function $f(x)=\exp_t(x)-1$ as coefficients of the polynomial terms of the taylor-series for $f^{°h}(x)$ (depending on iteration-height parameter $h$) see for instance description of the problem pg 12

It is also related to find a solution for the related problem in this older question at mathoverflow and my earlier attempt of an answer.

It appears you can do this with Smith normal form; in Newman's book Integral Matrices pages 37-38 he does the simpler $Ax=c$ where $A$ is rectangular but of maximal rank. Then he says take $UAV = [S;0]$ in Smith form; set $V^{-1}x = y$ and $Uc = d.$ Then we have $[S;0]y=d.$
The point is that $U,V$ are unimodular, also probably not that difficult to find in the first place. He says the same thing works for $Ax \equiv c \pmod m$ for nonzero integer $m.$
• Will, that's a very nice information - I've never experimented with the Smith-normal form. Luckily it is implemented in Pari/GP and I can try to get familiar with it by reading backed with try&error. Having the 3 components of the SNF of some $A_k$ now I've not yet an idea, how I can use it to find some "optimal" decomposition - but I'm chewing on it already... – Gottfried Helms Aug 18 '16 at 1:07
• @GottfriedHelms I was mostly thinking that Newman describes this for one column vector, there seemed no obstacle to performing the task for some $k$ column vectors making up an $n$ by $k$ rectangle. I suspect the part about less than maximal rank will take care of itself, some rows of zeros that can be removed... – Will Jagy Aug 18 '16 at 1:27