FINDING THE KERNEL OF A MATRIX WITH SYMBOLIC ENTRIES

Herbert S. Wilf

University of Pennsylvania

June 1, 1991, revised February 1, 1992

Abstract. Given a rectangular matrix A whose entries are polynomials in r variables over a field K, and an integer D. We give a recursive algorithm that finds a nontrivial vector in the kernel of A, if one exists whose entries are polynomials of degrees ≤ D in all variables. The algorithm involves only arithmetic over K, i.e., it avoids symbolic computation as such. It will be faster than previous algorithms if the degrees of the polynomial involved are less than about the square root of the size of the input matrix.

Let A be an m×n matrix whose entries are polynomials of degrees ≤ d in indeterminates t_{1}, …, t_{r}, over a field K, and let D be a given integer. We want to find a nontrivial x ∈ Ker(A), such that x has polynomial entries whose degree in each variable is ≤ D, if such an x exists.

Such questions are of importance in applications, for example in finding recurrence formulas satisfied by definite sums [W1], so it seems worthwhile to develop special methods that avoid the symbolic algebra as much as possible. Our plan here is to consider first the case r = 1, and then do the general case recursively. The result is an algorithm that will find x, while using only the standard functions of linear algebra, called on matrices whose entries lie in the ground field K. The result can be a considerable saving in time, though at a cost of space. In section 2 below we will compare the time complexity of our method with that of an earlier algorithm of McClellan [M].

1. The algorithm

If r = 1, then

A = A_{0} + A_{1}t + ⋯ + A_{d}t^{d},  (1)

in which the A_{i}’s have entries in K. We seek a nontrivial solution of Ax = 0. It is immediate, say from Cramer’s Rule, that Ker(A) has a basis whose vectors have polynomial entries all of whose degrees are at most D^{∗} = d min {m, n}. It frequently happens that

Typeset by AMS-TEX

Supported in part by the United States Office of Naval Research

there are nontrivial solutions whose degrees are much less than D^{∗}, so we will suppose that some trial degree D is given, 0 ≤ D ≤ D^{∗}, and that we want a computational procedure for finding a nontrivial solution vector of degree ≤ D, if one exists.

Let x = x_{0} + x_{1}t + x_{2}t^{2} + ⋯ + x_{D}t^{D} be such a vector. Then we have

\begin{aligned}0 & = Ax \\ & = ∑_{i=0}^{d} A_{i}t^{i} ∑_{j=0}^{D} x_{j}t^{j} \\ & = ∑_{k=0}^{d+D} t^{k}\{∑_{j} A_{k−j}x_{j}\}. \end{aligned}  (2)

Hence what we need is that

∑_{j=0}^{min {k,D}} A_{k−j}x_{j} = 0  (k = 0, …, d + D).  (3)

But these equations are equivalent to a single matrix-vector equation Âx̂ = ˆ0 in which Â is the matrix whose block structure is

Â = [ \begin{matrix}A_{0} & 0 & 0 & 0 & … & 0 & 0 \\ A_{1} & A_{0} & 0 & 0 & … & 0 & 0 \\ A_{2} & A_{1} & A_{0} & 0 & … & 0 & 0 \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ A_{d} & A_{d−1} & A_{d−2} & A_{d−3} & … & … & … \\ 0 & A_{d} & A_{d−1} & A_{d−2} & … & … & … \\ 0 & 0 & A_{d} & A_{d−1} & … & … & … \\ ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & 0 & 0 & 0 & … & 0 & A_{d} \end{matrix} ]  (4)

and whose size is m(d + D + 1) × n(D + 1).

Hence we can first find a nontrivial x̂ ∈ Ker(Â), then put (x_{0}, x_{1}, …, x_{D}) = x̂, and finally x = ∑_{j=0}^{D} x_{j}t^{j}, which solves the problem in the case of just one indeterminate. The running time of this algorithm will be

O(max {(m(d + D))^{α}, (nd)^{α}})

operations in the field K, where α is the exponent for the matrix multiplication problem.

Hence we began with a matrix A whose entries were of degrees d in t, and we constructed in (4) a new matrix Â, which we will now call stretch(A(t); d; D), to look for a kernel vector of degree D.

Let A be a matrix whose entries are polynomials in t_{1}, …, t_{r} with coefficients in K. Let d_{i} be the highest power of t_{i} that appears in A, for each i = 1, …, r, and let D be a positive integer. Then the matrix stretch(A(t); d_{r}; D) is the result of the construction (4), in which A_{i} is now the coefficient of t_{r}^{i} in A and d is now d_{r}. The entries of the stretch matrix are polynomials in t_{1}, …, t_{r−1}, so this leads to the following recursive procedure.

procedure findnullvec(A, r, d, D) % Given a matrix A whose entries are polynomials of degrees % at most d_{1}, …, d_{r} in variables t_{1}, …, t_{r}. % Returns a nontrivial vector x s.t. Ax = 0 and % s.t. the degrees of the entries of x are polynomials in % t_{1}, …, t_{r} of degrees at most D_{1}, …, D_{r}, if % such a vector exists; else returns 0.

If r = 0 do return a nontrivial vector x ∈ Ker(A), if one exists, else return 0

else do

z := (z_{0}, z_{1}, …, z_{D_{r}})

:= findnullvec(stretch(A, d_{r}, D_{r}), r − 1, d, D); if z = 0 then return 0

else return ∑_{j=0}^{D_{r}} z_{j}t_{r}^{j} □

2. Complexity analysis and comparison with earlier methods

(a) Time complexity. Concerning the time complexity of this procedure we have the following result.

Theorem. Let f_{r}(n, d, D) denote the number of arithmetic operations (i.e., operations on field elements) needed to implement this method on an input matrix whose larger dimension is n, whose entries contain r variables, none of which has degree higher than d, if we are looking for a kernel vector none of whose entries has degree higher than D. Then

f_{r}(n, d, D) = O((d + D + 1)^{rα}n^{α}),

where α ≤ 3 is the exponent for the matrix multiplication problem.

Indeed, the result follows by induction from the obvious recurrence

f_{r}(n, d, D) = O(f_{r−1}((d + D + 1)n, d, D),

and the initial condition f_{0}(n, d, D) = n^{α}. □

We will now try to compare our complexity estimate with that of McClellan’s procedure [M]. If we ignore certain logarithmic factors that convert number complexity to bit complexity, then his procedure will run in time O((n(d + 1))^{r}n^{a}) (in our notation), where a is a small integer. If we compare this with our estimate above we find that ours will be faster if (d + 1 + D)^{3} < n(d + 1). Hence very roughly, our procedure will be faster if the degrees of the variables involved are smaller than the square root of the size of the matrix. That is, the method works best on large matrices whose entries are of small degree.

(b) Space and program complexity.

Consider the space complexity of the program. The input matrix has mn entries each of which is a polynomial of degree d in r variables. Such a polynomial can have (d + 1)^{r} numerical coefficients, and therefore a total of mn(d + 1)^{r} coefficients appear in the input matrix.

After r recursive calls the size of the matrix will have grown to m(d + D + 1)^{r} rows by n(D + 1)^{r} columns, each containing a single coefficient. The total number of numerical coefficients that appear in the final stage is therefore at most

(\frac{(d + D + 1)(D + 1)}{d + 1})^{r}

times the number that appeared on input. The programming complexity of the method is virtually nil, since about a dozen instructions suffice.

References

[M] Michael T. McClellan, The exact solution of systems of linear equations with polynomial coefficients, J. Assoc. Comp. Mach. 20 (1973), 563–588.

[WZ] Herbert S. Wilf and Doron Zeilberger, An algorithmic proof theory for hypergeometric (ordinary and ‘q’) multisum/integral identities, Inventiones Mathematicæ (to appear).

Philadelphia, PA 19104-6395

E-mail address: wilf@central.cis.upenn.edu