DivisionFreeRowReduction Method for RowReduce

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?

• It does the forward reduction without division, then uses division to get pivots of 1, as this is required to produce the row echelon form. Apr 15, 2021 at 15:54
• Thank you very much for your insight! So for integers I could use of course HermiteDecomposition to get a reduced form without any divisions. Is anyone aware of a method to compute the nullspace truly division free? To me it seems a bit misleading if Nullspace[M,Method->"DivisionFreeRowReduction"] does divide. Apr 16, 2021 at 6:50

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.