0
$\begingroup$

I have two matrices A, B with same number of rows. I want lattice reduction on B. During this reduction, I change rows of A accordingly. That is if i-th row and j-th row in B interchanges, swap i-th row and j-th row of A. Similar for other elementary row operations.

How can I do efficiently this in Sage or other software?

  • 0
    If you were doing this by hand, you would probably form a large matrix with $B$ as the left block and $A$ as the right block. Then simply carry whichever row operations you wanted to do to this composite matrix. In the end you would separate the blocks again, and exact same row operations had been done to the two blocks. I am unfamiliar with Sage, so I don't know how easy it it is to form a matrix by combinining two blocks with its set of commands. @Martin may be able to say something more about that?2011-07-19

1 Answers 1

2

An easy, naive (but probably not effective) approach: If $C$ is obtained from $B$ using some row operations, this means that $C=RB$ for some regular matrix $R$.

If you select some columns of $C$ and the same columns of $B$ in a such way that you get a square regular matrix, you can compute $R=CB^{-1}$. As soon as you have $R$ you just need to multiply $RA$ to get what you want.

If you had your own implementation of the reduction algorithm, you could modify it easily in a such way, that it would also store the matrix $R$ somewhere. It is also possible, that the implementation in some math software computes this matrix. (I had a look at help for LLL-algorithm in Maple and Mathematica, but I did not find there anything about possibility of obtaining this matrix.)

  • 0
    Thank you all for the effort. Now I am trying to write LLL algorithm in Sage to solve the problem.2011-07-20