1
$\begingroup$

I would like to understand whether Gaussian elimination of an integer matrix, which uses only row operations of the form

  • Addition (or subtraction) of row $i$ to row $j$

can be performed in polynomial time.

Fraction-free Gaussian elimination can be demonstrated using such row operations by considering that these row operations generate the group $SL(2,\mathbf Z)$. Therefore, it is possible to perform operations on an an arbitrary column as

$$\left(\begin{matrix}a&b\\c&d\end{matrix}\right)$$

where the determinant $ad-cb=1$.

The $i$-th element of a matrix row can be reduced to $0$ by choosing $c,d$ such that

$$\left(\begin{matrix}a&b\\c&d\end{matrix}\right)\left(\begin{matrix}r_i\\r_j \end{matrix}\right)=\left(\begin{matrix}ar_i+br_j\\cr_i+dr_j \end{matrix}\right)=\left(\begin{matrix}ar_i+br_j\\0 \end{matrix}\right)$$

However, after $n$ iterations this results in exponential size matrix elements.

In the book [1] chapter 9.3 gives a "fraction-free" algorithm which shows that Gaussian elimination is possible for integer matrices by making use of the fact that common factors can be removed at each stage of the algorithm.

In the first "primitive" algorithm they suggest, they reduce common factors using the GCD of the row $i$ at each iteration. However, this would not correspond to an integer row additions. And so while this algorithm is fraction-free, it is not division free, in the sense that an additional row operation (i.e. dividing a row by some integer) is required in order to reduce the size of the elements and ensure polynomial time calculation.

However, what I do not understand is whether the next algorithm in the book given in (9.5) can be performed with only row additions.

Is a truly fraction free (and division free, in the sense of row division) Gaussian elimination possible in polynomial time?

[1] Geddes, K. O., Czapor, S. R., & Labahn, G. (1992). Algorithms for computer algebra. Springer Science & Business Media.

Improve this question
$\endgroup$
5
  • $\begingroup$ I assume you mean polynomial time in the number of bits. Can you reduce the column vector $[1; n]$ to $[1; 0]$ in fewer than $n$ row operations? $\endgroup$
    – Reid Barton
    Commented Nov 16, 2021 at 1:28
  • $\begingroup$ I actually mean polynomial both in the bits of the integers in the matrix, but also in the size of the dimension of the matrix. Perhaps that is the same thing, since we could write the matrix as a long bit string? But increasing the dimension of the matrix is what causes the exponential explosion in my example $\endgroup$
    – Cameron
    Commented Nov 16, 2021 at 7:24
  • $\begingroup$ @ReidBarton that case is pretty easy. The matrix [[a,b],[n,-1]] reduces [1;n] to [1;0]. Choosing a,b such that the determinant is $1$ results in picking a=-1, b=0 $\endgroup$
    – Cameron
    Commented Nov 16, 2021 at 7:29
  • $\begingroup$ So what you mean is that the operations are addition or subtraction of a multiple of row $i$ from row $j$. $\endgroup$
    – Aaron Meyerowitz
    Commented Nov 17, 2021 at 6:14
  • $\begingroup$ @AaronMeyerowitz Yes exactly, but my understanding was that the complexity of going from a row addition/subtraction by 1, to row addition/subtraction by n would be at most polynomial in $n$ $\endgroup$
    – Cameron
    Commented Nov 17, 2021 at 7:19

0

Reset to default

You must log in to answer this question.