3
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Apr 15, 2021 at 15:54
  • $\begingroup$ 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. $\endgroup$
    – blablablup
    Apr 16, 2021 at 6:50

1 Answer 1

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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