DivisionFreeRowReduction Method for RowReduce

Question

My overall goal is to use a division free algorithm to compute the nullspace of a matrix containing multivariate polynomials. For doing so, I believe, there is the method DivisionFreeRowReduction which can be also used for RowReduce. However, it seems to not actually do division free row reduction. Here are two examples:

M = {{x, x + y}, {y, 2*y}};
RowReduce[M, Method -> "DivisionFreeRowReduction"]

yields the identity matrix whereas one might expect something like $$ \begin{pmatrix} x & x+y \\ y & 2y\end{pmatrix} \to \begin{pmatrix} x & x+y \\ xy & 2xy\end{pmatrix} \to \begin{pmatrix} x & x+y \\ 0 & xy-2xy^2\end{pmatrix}.$$

The same is even true over the integres:

M2 = {{2, 3}, {4, 4}};
RowReduce[M2, Method -> "DivisionFreeRowReduction"]

yields the identity matrix, so it seems to divide.

What is going on? Why does the division free row reduction divide? How can you compute a nullspace using division free methods?

Answer 1

Try appending the Identity matrix to M and apply the row reduction to the larger matrix to recover the composite of the elementary row reductions:

Mprime = Join[M, IdentityMatrix[2], 2];
rrt = RowReduce[Mprime][[;; , 3 ;; 4]]

Then extract all of the divisions that were used in the row reduction:

denom = PolynomialLCM @@ Flatten[Denominator[rrt]]

Then undo the divisions that were used in the row reduction by clearing denominators:

rrtNoDivision=Simplify[denom*rrt]

The "no division" result you are seeking is rrtNoDivision.M using the row reduction transform rrtNoDivision.