0
$\begingroup$

I'm learning about the Bareiss algorithm to compute determinants over integral domains from Chee Yap, Fundamental Problems of Algorithmic Algebra (see also this question). The naive version of the algorithm suffers from zero divisions, i.e. it will not work if there are some leading principal minors that are 0.

As mentioned briefly in the text - and also more extensively in this paper (p. 34) - the workaround is to exchange rows (or columns, I guess this should be equivalent): If I'm in the k-th outermost step and the (k,k) entry is zero, I find a row i with i > k, such that the (i,k) entry is non-zero (and then multiply the determinant by -1).

Now my question is: What if I can't find any such row?

There is some hint later on in the Yap text about this meaning that the matrix has dependent rows (so the determinant would be 0). But I don't have a proof for this.

Additionally, it would be useful if somebody knew a concrete example of a matrix that exhibits this behaviour. The only one I can think of is the zero matrix which, trivially, does have determinant 0.

$\endgroup$
0
$\begingroup$

I believe I have now found a proof:

First, let's assume wlog that no row exchanges have happend up to the point where we cannot find a suitable row for the row exchange (because one can show that this would be equivalent to computing the determinant of the same matrix with the rows exchanged initially; that matrix has determinant 0 iff the original one has determinant 0). If, at the beginning of the $k$-th outermost iteration of the algorithm on a matrix $A$, we encounter an entry $a_{ik}$ mit $i \geq k$, then this is the determinant of the $(i,k)$-bordered matrix of order $k$ of $A$, i.e. of a $k\times k$ matrix (this can be shown by induction). Now assume $a_{ik} = 0$ for all $i\geq k$.

If $k=1$, the matrix $A$ would have a zero column, so the determinant must be zero. Otherwise, we look at the matrix $B$, which consists of the first $k$ columns of $A$. The first $k-1$ rows of $B$ can't be linearly dependent because otherwise they would also be dependent if we dropped the $k$-th column, so the leading principal minor of order $k-1$ would be zero - but that would mean that the $(k-1,k-1)$ entry of the modified matrix, after $k-1$ iterations, would be zero, which is impossible because then the algorithm would have been aborted before.

By assumption, the rows $1,\ldots,k-1,i$ of $B$ are dependent for any $i\geq k$. Since rows $1,\ldots,k-1$ are independent, this means that their span contains all other rows of $B$. Therefore, $B$ has rank $k-1$. But then $A$ can have rank at most $(k-1) + (n-k) = n-1$, which implies $|A| = 0$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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