0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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... $\endgroup$ – Gottfried Helms Aug 18 '16 at 1:07
  • $\begingroup$ @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... $\endgroup$ – Will Jagy Aug 18 '16 at 1:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.