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?
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.)