Question. I'm looking into certain algorithms for linear algebra which lie in NC2. Does anyone know of alternative references for the proof of the proposition just below, relating rank of matrices over R to characteristic polynomials over R(x)?

Proposition. Let A be an m×n matrix in a ring R, and let R(x) be the extension by a formal indeterminate x. Define the matrices $$\begin{align*} A' &= \begin{bmatrix} 0 & A \\ A^{\mathsf T} & 0 \end{bmatrix}, & X &= \mathrm{Diag}(1,x,x^2,\ldots,x^{m+n-1}), & B &= XA'\,.\end{align*}$$ Then rank(A) ≤ r for some integer r ≥ 0 if and only if the characteristic polynomial det(B − t I) of B is divisible by t 2(m+n−r).

Context. The proposition above is a standard result which allows decision problems about the rank of a matrix A to be reduced to those about the characteristic polynomial of B. A convincing proof of the proposition for the case that R is a finite field can be found in Mulmuley's article A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Because the degree of the formal indeterminate x can be bounded in det(B − t I), we can reduce this problem to a problem of polynomials over R alone.

While Mulmuley's proof breaks down for any ring that has nilpotent elements (such as 2 in the rings ℤ2k ), Allender + Beals + Ogihara claim (in their article The complexity of matrix rank and feasible systems of linear equations) that this proposition (or rather a result which I've paraphrased in the result above) holds generally for any ring, and is shown in the book chapter

J. von zur Gathen. "Parallel linear algebra". In J. H. Reif, editor, Synthesis of parallel algorithms, (pp. 573–617). Morgan Kaufmann, 1993.

which in any case is (or was) widely referenced in the literature. Unfortunately, I can't seem to locate a copy of it (physically embodied or otherwise) that does not require an investment of about $50, and a couple of weeks for shipping and handling, for the entire textbook.

Can anyone provide an alternative reference, or possibly show me where to find an inexpensive electronic copy of the one book chapter? I would be satisfied with any widely available standard text on abstract algebra which proved this proposition, for example.


Your Answer

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

Browse other questions tagged or ask your own question.