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.$