Generalizing Cramer’s Rule: Solving Uniformly Linear Systems of Equations

Gema M. Diaz–Toca^{∗} Dpto. de Matemática Aplicada Univ. de Murcia, Spain

                gemadiaz@um.es

Laureano Gonzalez–Vega^{∗} Dpto. de Matemáticas Univ. de Cantabria, Spain

                                         laureano.gonzalez@unican.es

Henri Lombardi ^{∗} Équipe de Mathématiques, UMR CNRS 6623 Univ. de Franche-Comté, France

                        henri.lombardi@univ-fcomte.fr

Abstract

Following Mulmuley’s Lemma, this paper presents a generalization of the Moore–Penrose Inverse for a matrix over an arbitrary field. This generalization yields a way to uniformly solve linear systems of equations which depend on some parameters.

Introduction

Given a system of linear equations over an arbitrary field 𝕂 with coefficient matrix A ∈ 𝕂^{m×n}, A x = v, the existence of solution depends only on the ranks of the matrices A and A|v. These ranks can be easily obtained by using Gaussian elimination, but this method is not uniform. When the entries of A and v depend on parameters, the resolution of the considered linear system may involve discussions on too many cases (see, for example, [18]).

Solving parametric linear systems of equations is an interesting computational issue encountered, for example, when computing the characteristic solutions for differential equations (see [5]), when dealing with coloured Petri nets (see [13]) or in linear prediction problems and in different applications of operation research and engineering (see, for example, [6], [8], [12], [15] or [19] where the elements of the matrix have a linear affine dependence on a set of parameters). More general situations where the elements are polynomials in a given set of parameters are encountered in computer algebra problems (see [1] and [18]).

In this paper we give a generalization of Mulmuley’s Algorithm (see [16]). If A ∈ 𝕂^{m×n}, we introduce the following matrix A^{∘} ∈ 𝕂(t)^{n×m}

A^{∘} = ( \begin{matrix}1 & 0 & … & 0 \\ 0 & t^{−1} & … & 0 \\ ⋮ & ⋮ & & ⋮ \\ 0 & 0 & … & t^{−(n−1)} \end{matrix} ) A^{t} ( \begin{matrix}1 & 0 & … & 0 \\ 0 & t & … & 0 \\ ⋮ & ⋮ & & ⋮ \\ 0 & 0 & … & t^{m−1} \end{matrix} ) ,

∗Partially supported by the European Union funded project RAAG (HPRN–CT–2001–00271) and by the spanish grant BFM2002-04402-C02-0

where t is a new variable. Next we define the Generalized Gram’s Polynomials of A as the coefficients of the characteristic polynomial of A A^{∘}, which are Laurent polynomials in the variable t. From the Generalized Gram’s Polynomials it is possible in a very uniform and compact way:

1. to characterize the rank of A and,

2. once the rank of A is fixed, to determine:

(a) matrices associated with precise projections of 𝕂(t)^{m} onto Im A and of 𝕂(t)^{n} onto Ker A respectively,

(b) the equations of Im(A),

(c) a Generalized Moore–Penrose Inverse of A, and

(d) given v ∈ Im(A), a solution of A x = v generalizing the classical Cramer’s Rule to the underdetermined and overdetermined cases via our Generalized Moore–Penrose Inverse.

This provides a generalization of the classical Moore-Penrose Inverse and Gram’s Coefficients in the real or complex cases. The surprising fact is that for non real fields (e.g., fields of characteristic p) the rank of any matrix and a uniform generalized inverse of the matrix can be also controlled by a small number of sums of squares of minors.

In fact our Generalized Gram’s Polynomials are only slight variants of the polynomials that appear in Mulmuley’s Algorithm.

A consequence of this method is, as in [16], that the characterization of a full rank matrix in 𝕂^{m×n} (for any field 𝕂) can be done by using less than min(n, m)|n − m| + 1 polynomials in the entries of A: each one of these polynomials is a sum of squares of maximal minors of A. If n = 2m then min(n, m)|n − m| + 1 = m^{2} + 1, which is clearly far from the consideration of the \binom{n}{m} maximal minors of A.

In general, the total number of sums of squares of minors to be used for characterizing the rank is smaller than \frac{1}{2}p(p + 1)p′, where p = min(m, n) and p′ = max(m, n), so it is bounded by O(p′ p^{2}); note that the total number of minors is clearly bigger than 2^{p} (\frac{p′}{p})^{\frac{p}{2}} .

Compared to Mulmuley’s Method, an important (and new) characteristic of the proposed method is the generalization of Moore–Penrose Inverses for each possible rank r. This allows us to obtain a uniform solving of linear systems of equations once the rank is known. Moreover, this is particularly useful when linear systems of equations depend on some parameters (avoiding thus any discussion on the vanishing or not of the pivots to be used; see the last section for enlightening examples).

Our method requires a complexity similar to the one given in [11], where the parameterized Gauss elimination is analyzed, and it is proved that with k parameters, the complexity of parametric solving of A x = v is in n^{O(k)}.

The paper is organized as follows. The first section recalls the classical theory about generalized inverses matrices. In the second section, we introduce a generalization of both Gram Coefficients and of Moore–Penrose Inverse matrix for an arbitrary field. Finally, the third section presents three different examples, where we apply the different results described in the second section.

1 Gram Coefficients and Moore-Penrose Inverse in real or complex case

This section is devoted to introducing some important theoretical points of Gram Coefficients and Moore–Penrose Inverse in the real or complex cases.

In [2, 3, 10, 14, 17], one can find different approaches to studying generalized inverses. In [7], one can find precise proofs of the results appearing in this section.

1.1 General theory

Let 𝕂 be either the real or the complex field, E = 𝕂^{n}, F = 𝕂^{m} and let L(E, F) denote the set of all linear transformations of E into F. If H is a linear subspace of E, we denote by π_{H} : E → E the orthogonal projection on H.

Let φ ∈ L(E, F) and let A ∈ 𝕂^{m×n} be a matrix representation of φ with respect to orthonormal bases. If ⟨x, y⟩ denotes the inner product of x and y, the conjugate transpose A^{⋆} of A represents the adjoint transformation φ^{⋆} such that:

∀x ∈ E ∀y ∈ F  ⟨φ(x), y⟩_{F} = ⟨x, φ^{⋆}(y)⟩_{E}  (1)

The results recalled here are based on the following lemma.

Lemma 1.1 If A ∈ 𝕂^{m×n} then:

Im A ⊕ Ker A^{⋆} = F,  Ker A ⊕ Im A^{⋆} = E .  (2)

The matrices AA^{⋆} and A^{⋆}A are positive semi-definite matrices and in general they may be singular.

Definition 1.2 The Gram’s Coefficients of A are defined to be the coefficients G_{k}(A) = a_{k} of the polynomial:

det(I_{m} + z AA^{⋆}) = 1 + a_{1} z + ⋯ + a_{m} z^{m},  (3)

where z is a variable. We also define G_{0}(A) = 1 and G_{ℓ}(A) = 0 if ℓ > m.

If Q(z) = det(I_{m} + z A A^{⋆}) then det(zI_{m} − A A^{⋆}) = (−1)^{m}z^{m}Q(1/z). Hence the Gram’s Coefficients of A are, except signs, the coefficients of the characteristic polynomial of AA^{⋆}.

Lemma 1.3 (Gram’s Conditions for rank) 1. rk(A) ≤ r ⟺ G_{r+1}(A) = 0 ⟺ ⋀_{k>r} G_{k}(A) =

0.

2. rk(A) = r ⟺ G_{r+1}(A) = 0 ≠ G_{r}(A).

In the sequel we assume r = rk(A). So det(I_{m} + z A A^{⋆})= det(I_{n} + z A^{⋆} A) = 1 + a_{1} z +…+ a_{r} z^{r} . The use of Cayley–Hamilton Theorem yields the following lemma.

Lemma 1.4 (orthogonal projections onto the image and onto the kernel) 1. The orthogonal projection π_{I} onto the subspace I = Im A ⊆ F is equal to:

π_{I} = a_{r}^{−1} (a_{r−1}A A^{⋆} − a_{r−2}(A A^{⋆})^{2} + ⋯ + (−1)^{r−1}(A A^{⋆})^{r}) .  (4)

2. The orthogonal projection π_{I^{⋆}} onto the subspace I^{⋆} = Im A^{⋆} ⊆ E is equal to:

π_{I^{⋆}} = a_{r}^{−1} (a_{r−1}A^{⋆}A − a_{r−2}(A^{⋆}A)^{2} + ⋯ + (−1)^{r−1}(A^{⋆}A)^{r}) .  (5)

And the orthogonal projection onto the kernel of A is I_{n} − π_{I^{⋆}}.

Let φ_{0} be the linear isomorphism from Im A^{⋆} to Im A, defined by the restriction of φ.

Definition 1.5 Suppose rk(A) = r. The Moore–Penrose Inverse of A in rank r is the linear transformation φ^{†^{r}} : F → E defined by:

∀y ∈ F, φ^{†^{r}}(y) = φ_{0}^{−1}(π_{Im A}(y)).

Let A^{†^{r}} be the matrix associated with φ^{†^{r}}.

Proposition 1.6 (The Moore–Penrose Inverse) Assume rk(A) = r. Let v ∈ F. Then:

1. A^{†^{r}} ∈ 𝕂^{n×m} is given by:

\begin{aligned}A^{†^{r}} & = & a_{r}^{−1} (a_{r−1}I_{n} − a_{r−2}(A^{⋆} A) + ⋯ + (−1)^{r−1}(A^{⋆} A)^{r−1}) A^{⋆} \\ & = & a_{r}^{−1} A^{⋆} (a_{r−1}I_{m} − a_{r−2}(A A^{⋆}) + ⋯ + (−1)^{r−1}(A A^{⋆})^{r−1}) \end{aligned}  (6)

Moreover, A = A A^{†^{r}} A, A^{†^{r}} = A^{†^{r}} A A^{†^{r}}, π_{I} = A A^{†^{r}} and π_{I^{⋆}} = A^{†^{r}} A.

2. The linear system A x = v has a solution if and only if G_{r+1}(A|v) = 0.

3. If v ∈ Im A, then:

v = A A^{†^{r}} v  (7)

and x = A^{†^{r}} v is one solution of the linear system A x = v. Moreover, it is the only solution in the linear space generated by the columns of A^{⋆}, that is, its norm is minimal.

Note that Equation (6) can be viewed as a definition of the matrix A^{†^{r}} ∈ 𝕂^{n×m}, only requiring rk(A) ≥ r, that is a_{r} ≠ 0. This fact is useful in numerical analysis when the coefficients of A are real numbers known with finite precision that implies some doubts about the rank of the matrix.

1.2 Cramer Identities

In this subsection, we give a description of the Moore–Penrose Inverse as a weighted sum of Cramer Identities.

Lemma 1.7 The Gram’s Coefficient G_{k}(A) is equal to the sum of squares of modulus of k–minors of the matrix A.

Observe that this lemma provides another way to understand Lemma 1.3. In the following, we only consider the real case. Obvious modifications have to be made in the complex case. Suppose rk(A) = r and v ∈ Im A.

Notation 1.8 • A_{j} denotes the j–th column of A.

• A_{α,β} denotes the submatrix of A where the rows and columns retained are given by subscripts α = {α_{1}, …, α_{r}} ⊂ {1, …, m} and β = {β_{1}, …, β_{r}} ⊂ {1, …, n} respectively.

• A_{1: m,β} denotes the submatrix of A retaining the columns given by β. A_{α,1: n} denotes the submatrix of A retaining the rows given by α.

• μ_{α,β} denotes the r–minor, determinant of A_{α,β}.

• Given j ∈ {1, …, r}, let σ_{α,β,j} denote the determinant of A_{α,β} but replacing the j–th column with the column obtained from v retaining the rows α.

• Let Adj_{α,β}(A) = (I_{n})_{1: n,β} Adj(A_{α,β}) (I_{m})_{α,1: m} .

Then for every subscript pair (α, β), since rk(A|v) = r, we obtain a Cramer’s Identity:

μ_{α,β} v = ∑_{j=1}^{r} σ_{α,β,j} A_{β_{j}} = ( A_{β_{1}} … A_{β_{r}} ) ( σ_{α,β,1} ; ⋮ ; σ_{α,β,r} ) =

= ( A_{β_{1}} … A_{β_{r}} ) Adj(A_{α,β}) ( v_{α_{1}} ; ⋮ ; v_{α_{r}} ) =
= A (I_{n})_{1: n,β} Adj(A_{α,β}) (I_{m})_{α,1: m} v = A Adj_{α,β}(A) v,

that is

μ_{α,β} v = A Adj_{α,β}(A) v.  (8)

Since G_{r}(A) = ∑_{α,β} μ_{α,β}^{2} ≠ 0, where the summation extends over all \binom{n}{r}\binom{m}{r} distinct sets of rows and columns indices, by multiplying every equality (8) by μ_{α,β} and by adding up all these equalities, we obtain the following expression:

G_{r}(A) v = A (∑_{α,β} μ_{α,β} Adj_{α,β}(A)) v,  (9)

which is highly similar to Equation (7) in Proposition 1.6. Indeed Equation 2.13 in [17] applied to our case yields:

A^{†^{r}} = G_{r}(A)^{−1} ∑_{β,α} μ_{α,β} Adj_{α,β}(A).  (10)

interpreted as a weighted sum of Cramer Identities.

2 Generalization for an arbitrary field

This section is devoted to presenting a generalization of Gram Coefficients and Moore–Penrose Inverse matrix for an arbitrary field 𝕂. Our work can be seen as an extension of the result of Mulmuley:

Lemma 2.1 (Mulmuley’s Algorithm) Let P ∈ 𝕂^{n×n} be a symmetric matrix, t a variable and Q_{n} = diag(1, t, t^{2}, …, t^{n−1}). If P̃ = P Q_{n} and c_{k}(t) is the coefficient of z^{n−k} in the characteristic polynomial of P̃, then the rank of the matrix P is smaller or equal to r if and only if c_{k}(t) = 0 for k > r.

The classical results introduced in Section 1.1 are based on orthogonal sums of images and kernels of A ∈ 𝕂^{m×n} and A^{⋆} ∈ 𝕂^{n×m} (Equation 2).

So, if we consider vector spaces over an arbitrary field 𝕂, all the results would similarly work if we were able to define a good inner product and some suitable φ^{∘} : F → E satisfying (2) and if we replace the expression orthogonal projection onto Im φ by projection onto Im φ parallel to Ker(φ^{∘}).

2.1 General theory

With the purpose of generalizing Equation (2) for an arbitrary field 𝕂, we have to introduce a parameter t and to work over the field 𝕂(t). Next we define the quadratic form Φ_{t,n} on E′ = 𝕂(t)^{n} with values in 𝕂(t) as

Φ_{t,n}(ξ_{1}, …, ξ_{n}) = ξ_{1}^{2} + t ξ_{2}^{2} + ⋯ + t^{n−1} ξ_{n}^{2} ,

and the quadratic form Φ_{t,m} on F′ = 𝕂(t)^{m} with values in 𝕂(t) as

Φ_{t,m}(ζ_{1}, …, ζ_{m}) = ζ_{1}^{2} + t ζ_{2}^{2} + ⋯ + t^{m−1} ζ_{m}^{2} .

The “associated inner products” with Φ_{t,n} and Φ_{t,m}, denoted by ⟨·, ·⟩_{E′} and ⟨·, ·⟩_{F′} respectively, lead us to the wanted linear transformation φ^{∘} in a natural way.

Given a 𝕂–linear transformation φ ∈ L(E, F), we get by extension of scalars a 𝕂(t)–linear transformation φ′ in L(E′, F′). The matrix A of φ is the same as the matrix of φ′.

Thus, there exists only one linear transformation, A^{∘} : F′ → E′, which verifies:

∀x ∈ E′, ∀y ∈ F′,  ⟨A x, y⟩_{F′} = ⟨x, A^{∘} y⟩_{E′}  (11)

which is very similar to Equation (1).

If Q_{n} = diag(1, t, t^{2}, …, t^{n−1}) and Q_{m} = diag(1, t, t^{2}, …, t^{m−1}) are the diagonal matrices associated with ⟨·, ·⟩_{E′} and ⟨·, ·⟩_{F′} respectively, A^{∘} is given by

A^{∘} = Q_{n}^{−1} A^{t} Q_{m}.

Hence, for all x ∈ 𝕂(t)^{n×1}, y ∈ 𝕂(t)^{m×1}, we have (A x)^{t} Q_{m} y = x^{t} Q_{n} (A^{∘} y).

In practice, if A = (a_{i,j}), then A^{∘} = (t^{j−i} a_{j,i}); for instance:

A = [ \begin{matrix}a_{11} & a_{12} & a_{13} & a_{14} & a_{15} \\ a_{21} & a_{22} & a_{23} & a_{24} & a_{25} \\ a_{31} & a_{32} & a_{33} & a_{34} & a_{35} \end{matrix} ] , A^{∘} = [ \begin{matrix}a_{11} & t a_{21} & t^{2} a_{31} \\ t^{−1} a_{12} & a_{22} & t a_{32} \\ t^{−2} a_{13} & t^{−1} a_{23} & a_{33} \\ t^{−3} a_{14} & t^{−2} a_{24} & t^{−1} a_{34} \\ t^{−4}a_{15} & t^{−3}a_{25} & t^{−2}a_{35} \end{matrix} ]

Furthermore (A^{∘})^{∘} = A and (A B)^{∘} = B^{∘} A^{∘}. Next we state and prove the following key lemma.

Lemma 2.2 With the previous notation:

Im A ⊕ Ker A^{∘} = F′ , Ker A ⊕ Im A^{∘} = E′.  (12)

Thus,

Im A = Im A A^{∘} ,  Ker A^{∘} = Ker A A^{∘} ,
Ker A = Ker A^{∘}A ,  Im A^{∘} = Im A^{∘}A .

(13)

Proof 2.3 Clearly A and A^{∘} have same rank, so we only need to prove

Im A ∩ Ker A^{∘} = {0} and Im A^{∘} ∩ Ker A = {0}.

Equation (11) implies that:

• the orthogonal subspace of Im A (w.r.t. the bilinear form ⟨·, ·⟩_{F′}) is equal to Ker A^{∘}, and

• the orthogonal subspace of Im A^{∘} (w.r.t. the bilinear form ⟨·, ·⟩_{E′}) is equal to Ker A but, since ⟨·, ·⟩_{E′} is a non–degenerate bilinear form, the orthogonal subspace of Ker A (w.r.t. the bilinear form ⟨·, ·⟩_{E′}) is equal to Im A^{∘}.

Moreover Im A and Ker A are defined over 𝕂 inside F and E. So, it is enough to prove the following statement:

Given a 𝕂–subspace H_{1} of F (resp. of E), if H is the 𝕂(t)–subspace of F′ (resp. of E′)

generated by H_{1} then H ∩ H^{⊥} = {0}.

Suppose that (p_{1}(t), …, p_{m}(t)) ∈ H ∩ H^{⊥} and (p_{1}(t), …, p_{m}(t)) ∈ 𝕂[t]^{m}. Let v_{1}, …, v_{s} ∈ 𝕂^{m} be a basis in H_{1} and a_{1}(t), …, a_{s}(t) ∈ 𝕂(t) such that

(p_{1}(t), …, p_{m}(t)) = ∑_{i} a_{i}(t) v_{i}.

Let u be a new unknown and let us work in 𝕂[t, u]. Since ∑_{i} a_{i}(t) v_{i} ∈ H^{⊥}, it follows:

P (t, u) = ⟨∑_{i} a_{i}(t) v_{i}, ∑_{i} a_{i}(u) v_{i}⟩_{F′} = ∑_{i=1}^{m} p_{i}(t) p_{i}(u) t^{i−1} = 0.

Now we deduce from the last equality that p_{i}(t) = 0 for every i. We present a proof by induction on the highest degree of p_{i}’s.

If ∀i, deg(p_{i}(t)) = 0 then the statement is easily verified. In the general case, we first see that the independent coefficient of the p_{i}’s are zero. The equality P (0, 0) = p_{1}(0)^{2} implies that p_{1}(0) = 0. And if p_{1}(0) = ⋯ = p_{k}(0) = 0 then the coefficient of t^{k} in P (t, u) is equal to p_{k+1}(0)^{2} and therefore p_{k+1}(0) = 0. We conclude that all the independent coefficients are zero and every p_{i}(t) is divisible by t. So the result follows by induction.

Note that this proof is based on the one for Mulmuley’s Lemma in [16].

Lemma 2.2 is the analog of Lemma 1.1. This allows us to generalize Definitions 1.2 and 1.5, Lemmas 1.3 and 1.4 and Proposition 1.6 in the following way.

A A^{∘} are in the Laurent polynomial ring 𝕂[t, 1/t].

Definition 2.4 The Generalized Gram’s Polynomials, G′_{k}(A)(t) = a_{k}(t) ∈ 𝕂[t, 1/t], and the Generalized Gram’s Coefficients, G′_{k,ℓ}(A) = a_{k,ℓ} ∈ 𝕂, are given by the following expression:

\{ \begin{matrix}det(I_{m} + z AA^{∘}) & = & 1 + a_{1}(t) z + ⋯ + a_{m}(t) z^{m} \\ a_{k}(t) & = & t^{−k(n−k)} ( ∑_{ℓ=0}^{k(m+n−2k)} a_{k,ℓ} t^{ℓ}) . \end{matrix}  (14)

Observe that if the matrix A is real, usual Gram’s Coefficients are given by:

G_{k}(A) = G′_{k}(A)(1) = ∑_{ℓ} a_{k,ℓ}.  (15)

If p = min(m, n) and p′ = max(m, n), then the total number of Generalized Gram’s Coefficients is equal to:

∑_{k=1}^{p} (k (m + n − 2k) + 1) = p + \frac{1}{6} p (p + 1) (3p′ − p − 2) ≤ \frac{1}{2}p(p + 1)p′ .

Generalized Gram’s Coefficients provide the rank of the given matrix, generalizing Lemma 1.3.

Lemma 2.5 (Generalized Gram’s Conditions for the rank)

1. rk(A) ≤ r ⟺ ⋀_{k>r} G′_{k}(A)(t) = 0.

2. rk(A) = r ⟺ ⋀_{k>r} G′_{k}(A)(t) = 0 ∧ G′_{r}(A)(t) ≠ 0.

This can be seen as a reformulation of the key result in [16]. Similarly, we can generalize Lemma 1.4.

Lemma 2.6 (orthogonal projections onto the image and onto the kernel)

Let a_{k}(t) = G′_{k}(A). If rk(A) = r then:

1. The projection onto the subspace Im A ⊆ F′ parallel to Ker A^{∘} is the orthogonal projection with respect to ⟨ , ⟩_{F′} and is given by:

π_{Im A} = a_{r}^{−1} (a_{r−1}AA^{∘} − a_{r−2}(AA^{∘})^{2} + ⋯ + (−1)^{r−1}(AA^{∘})^{r}) .  (16)

2. The projection onto the subspace Im A^{∘} ⊆ E′ parallel to Ker A is the orthogonal projection with respect to ⟨ , ⟩_{E′} and is given by:

π_{Im A^{∘}} = a_{r}^{−1} (a_{r−1}A^{∘}A − a_{r−2}(A^{∘}A)^{2} + ⋯ + (−1)^{r−1}(A^{∘}A)^{r})  (17)

and the projection onto Ker A parallel to Im A^{∘} is I_{n} − π_{Im A^{∘}}.

Remark 2.7 Actually the unknown t can be replaced in every formula with any value τ ∈ 𝕂 which does not cause the denominator a_{r}(t) to vanish (always possible if the field 𝕂 has more than r(m+n−2r)+1 elements).

Let φ_{0} be the linear isomorphism from Im A^{∘} ⊂ E′ to Im A ⊂ F′, which is the restriction of φ′. Next we introduce the generalization of the Moore–Penrose Inverse.

Definition 2.8 Suppose rk(A) = r. The Generalized Moore–Penrose Inverse of A in rank r is the linear transformation φ^{†^{r,t}} : F′ → E′ defined by:

∀y ∈ F′, φ^{†^{r,t}}(y) = φ_{0}^{−1}(π_{Im A}(y)).

Let A^{†^{r,t}} be the matrix associated with φ^{†^{r,t}}.

Next result shows how to obtain the Generalized Moore–Penrose Inverse of A for an arbitrary field and it is the most important result presented in the paper.

Theorem 2.9 (Generalized Moore–Penrose Inverse) Let a_{k}(t) = G′_{k}(A), v ∈ F and rk(A) = r. Then

1. The Generalized Moore–Penrose Inverse of A ∈ 𝕂^{m×n} in rank r is given by:

A^{†^{r,t}} = a_{r}^{−1} (a_{r−1}I_{n} − a_{r−2}A^{∘}A + ⋯ + (−1)^{r−1}(A^{∘}A)^{r−1}) A^{∘}  (18)

Moreover, A A^{†^{r,t}} A = A, A^{†^{r,t}} A A^{†^{r,t}} = A^{†^{r,t}}, A A^{†^{r,t}} = π_{Im A} and A^{†^{r,t}} A = π_{Im A^{∘}}.

2. The linear system Ax = v has a solution if and only if G′_{r+1}(A|v) = 0.

3. If v ∈ Im A, then:

v = A A^{†^{r,t}} v  (19)

and x = A^{†^{r,t}} v is one solution of the linear system A x = v. Moreover, it is the only solution in the linear space generated by the columns of A^{∘}.

Corollary 2.10

i) If A is injective (i.e., r = n) and v ∈ Im A, the vector A^{†^{r,t}} v is the only solution of the corresponding linear system. Therefore, it does not depend on t and the coordinates of A^{†^{r,t}} v, which are, a priori, rational functions on the variable t, are in fact in 𝕂: computing the divisions of the numerators by the denominator returns constants. ii) Given A^{†^{r,t}} by Equation (18), if we define

B_{r} = a_{r}(t) A^{†^{r,t}} = ∑ B_{r,k}t^{k}, B_{r,k} ∈ 𝕂^{n×m},

then A B_{r,k} A = a_{r,k} A.

Moreover, for every a_{r,k} ≠ 0, we can define

C_{r,k} = 1/a_{r,k} B_{r,k}, D_{r,k} = C_{r,k} A C_{r,k},

and then it is easily checked that the matrix D_{r,k} satisfies the equations

A D_{r,k} A = A, D_{r,k} A D_{r,k} = D_{r,k}.

Thus, we can conclude that D_{r,k} ∈ 𝕂^{n×m} is a generalized inverse of A and so:

(a) If v ∈ Im(A), then D_{r,k} v is a solution of A x = v,

(b) A D_{r,k} is a projection onto Im A, and

(c) I − D_{r,k} A is a projection onto Ker A.

For more details see [7].

2.2 Generalizing Cramer Identities

Next, we introduce a description of the Generalized Gram’s Coefficients of A as sums of squares of minors.

Lemma 2.11 Let A ∈ 𝕂^{m×n} ⊆ 𝕂(t)^{m×n} and μ_{α,β} be the k–minor where the rows and columns retained are given by subscripts α = {α_{1}, …, α_{k}} ⊂ {1, …, m} and β = {β_{1}, …, β_{k}} ⊂ {1, …, n}. If S_{m,n,k,ℓ} is defined as:

S_{m,n,k,ℓ} = {(α, β) | |α| − |β| = ℓ − k(n − k)} ,

then the Generalized Gram’s Coefficient a_{k,ℓ} = G′_{k,ℓ}(A) is given by:

G′_{k,ℓ}(A) = ∑_{(α,β)∈S_{m,n,k,ℓ}} μ_{α,β}^{2}.  (20)

By the same reasoning as in the previous section, we obtain Equation (8). Thus, if for every (α, β) in S_{m,n,k,ℓ}, we multiply both sides of Equation (8) by μ_{α,β} t^{|α|−|β|} and add up all these equalities, we obtain the following expression:

G′_{r}(A) v = A (∑_{α,β} μ_{α,β} t^{|α|−|β|} Adj_{α,β}(A)) v  (21)

which is very close to Equation (19) in Proposition 2.9. In fact, by applying Equation 2.13 in [17], we get:

Proposition 2.12 Let A ∈ 𝕂^{m×n}, then:

A^{†^{r,t}} = G′_{r}(A)^{−1} ∑_{α,β} μ_{α,β} t^{|α|−|β|} Adj_{α,β}(A).  (22)

As in the usual case, Equation (22) shows that the Generalized Moore–Penrose Inverse can be interpreted as a weighted sum of Cramer Identities. Observe that if we evaluate Equation (22) at t = 1, then we find out the theory of the Moore–Penrose Inverse in the real case.

2.3 Case of symmetric matrices

If A = A^{t} , there is a more simplified expression for its generalized Moore-Penrose Inverse than Equation (18). So, assume that E = F, rk(A) = r and A = A^{t}. Since A is symmetric, A^{∘} = Q_{n}^{−1} A Q_{n}. Let Ã = A Q_{n}. Then,

Im Ã = Im A,  Ker Ã = Ker A^{∘},
Im A = Im(Q_{n} A^{∘}), Ker A = Q_{n}(Ker A^{∘})

and Equation (12) can be rewritten as the orthogonal decomposition with respect to ⟨·, ·⟩_{E′}:

Im Ã ⊕ Ker Ã = Im A ⊕ Ker A^{∘} = E′.

Let φ̃_{0} denote the linear automorphism of Im A obtained as restriction of Ã. So A, Ã and φ_{0} have the same rank r, and the direct sum Im Ã ⊕ Ker Ã = E′ implies the following:

det(I_{n} + z Ã) = 1 + b_{1}(t)z + ⋯ + b_{r}(t)z^{r} ,  (23)

with b_{r} ≠ 0 and b_{r+1} = … = b_{n} = 0. As a result, the Mulmuley’s Lemma is derived, as it was expected, and we have the following simplified versions of the previous results.

Proposition 2.13 (Generalized Moore–Penrose Inverse in the symmetric case) 1. The orthogonal projection π_{Im} A onto the subspace Im A of E′ with respect to ⟨ , ⟩_{E′} is equal to:

π_{Im A} = b_{r}^{−1} (b_{r−1} Ã − b_{r−2} Ã^{2} + ⋯ + (−1)^{r}b_{1} Ã^{r−1} + (−1)^{r+1}Ã^{r}) .

2. We have A^{†^{r,t}} = Q_{n} Ã^{†^{r,t}} and Ã^{†^{r,t}} is given by:

Ã^{†^{r,t}} = b_{r}^{−1} (b_{r−1} π_{Im A} − b_{r−2} Ã + ⋯ + (−1)^{r}b_{1} Ã^{r−2} + (−1)^{r+1}Ã^{r−1}) .

In [3], similar formulas for classical Moore–Penrose Inverses of hermitian matrices can be found.

3 The shape of the Generalized Cramer’s Rule: examples

3.1 Cramer’s Rule for underdetermined systems of linear equations

For the underdetermined system of linear equations,

( \begin{matrix}a_{1,1} & a_{1,2} & a_{1,3} \\ a_{2,1} & a_{2,2} & a_{2,3} \end{matrix} ) ( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \end{matrix} ) = ( \begin{matrix}b_{1} \\ b_{2} \end{matrix} ) ,  (24)

the Generalized Gram’s Polynomials are given by det(I_{2} + zA A^{∘}):

\begin{aligned}1 & + (a_{2,1}^{2}t + (a_{1,1}^{2} + a_{2,2}^{2}) + \frac{a_{1,2}^{2} + a_{2,3}^{2}}{t} + \frac{a_{1,3}^{2}}{t^{2}} ) z \\ & + (| \begin{matrix}a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2} \end{matrix} |^{2} + \frac{| \begin{matrix}a_{1,1} & a_{1,3} \\ a_{2,1} & a_{2,3} \end{matrix} |^{2}}{t} + \frac{| \begin{matrix}a_{1,2} & a_{1,3} \\ a_{2,2} & a_{2,3} \end{matrix} |^{2}}{t^{2}} ) z^{2}. \end{aligned}

Thus the matrix A has rank • equal to 2 if and only if the polynomial

| \begin{matrix}a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2} \end{matrix} |^{2} + \frac{| \begin{matrix}a_{1,1} & a_{1,3} \\ a_{2,1} & a_{2,3} \end{matrix} |^{2}}{t} + \frac{| \begin{matrix}a_{1,2} & a_{1,3} \\ a_{2,2} & a_{2,3} \end{matrix} |^{2}}{t^{2}}  (25)

is not zero,

• equal to 1 if and only if the polynomial in (25) vanishes identically and the polynomial

a_{2,1}^{2}t + (a_{1,1}^{2} + a_{2,2}^{2}) + \frac{a_{1,2}^{2} + a_{2,3}^{2}}{t} + \frac{a_{1,3}^{2}}{t^{2}}  (26)

is not zero, and

• equal to 0 if and only if both polynomials (25) and (26) vanish identically.

Assuming rank(A) = 2, the (simplified) solution of the considered system is presented “á la Cramer” by the following expressions describing a rational curve in 𝕂^{3}:

\begin{aligned}x_{1}(t) & = & \frac{| \begin{matrix}a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2} \end{matrix} | | \begin{matrix}b_{1} & a_{1,2} \\ b_{2} & a_{2,2} \end{matrix} | + \frac{| \begin{matrix}a_{1,1} & a_{1,3} \\ a_{2,1} & a_{2,3} \end{matrix} | | \begin{matrix}b_{1} & a_{1,3} \\ b_{2} & a_{2,3} \end{matrix} |}{t}}{| \begin{matrix}a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2} \end{matrix} |^{2} + \frac{| \begin{matrix}a_{1,1} & a_{1,3} \\ a_{2,1} & a_{2,3} \end{matrix} |^{2}}{t} + \frac{| \begin{matrix}a_{1,2} & a_{1,3} \\ a_{2,2} & a_{2,3} \end{matrix} |^{2}}{t^{2}}} \\ x_{2}(t) & = & \frac{| \begin{matrix}a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2} \end{matrix} | | \begin{matrix}a_{1,1} & b_{1} \\ a_{2,1} & b_{2} \end{matrix} | + \frac{| \begin{matrix}a_{1,2} & a_{1,3} \\ a_{2,2} & a_{2,3} \end{matrix} | | \begin{matrix}b_{1} & a_{1,3} \\ b_{2} & a_{2,3} \end{matrix} |}{t^{2}}}{| \begin{matrix}a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2} \end{matrix} |^{2} + \frac{| \begin{matrix}a_{1,1} & a_{1,3} \\ a_{2,1} & a_{2,3} \end{matrix} |^{2}}{t} + \frac{| \begin{matrix}a_{1,2} & a_{1,3} \\ a_{2,2} & a_{2,3} \end{matrix} |^{2}}{t^{2}}} \\ x_{3}(t) & = & \frac{\frac{| \begin{matrix}a_{1,1} & a_{1,3} \\ a_{2,1} & a_{2,3} \end{matrix} | | \begin{matrix}a_{1,1} & b_{1} \\ a_{2,1} & b_{2} \end{matrix} |}{t} + \frac{| \begin{matrix}a_{1,2} & a_{1,3} \\ a_{2,2} & a_{2,3} \end{matrix} | | \begin{matrix}a_{1,2} & b_{1} \\ a_{2,2} & b_{2} \end{matrix} |}{t^{2}}}{| \begin{matrix}a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2} \end{matrix} |^{2} + \frac{| \begin{matrix}a_{1,1} & a_{1,3} \\ a_{2,1} & a_{2,3} \end{matrix} |^{2}}{t} + \frac{| \begin{matrix}a_{1,2} & a_{1,3} \\ a_{2,2} & a_{2,3} \end{matrix} |^{2}}{t^{2}}} \end{aligned}  (27)

Algebraically these expressions verify the system in (24) providing thus a rational curve in 𝕂^{3} giving a solution for (24) for every value of the parameter t (not vanishing the denominator).

Knowing, for example, that

| \begin{matrix}a_{1,2} & a_{1,3} \\ a_{2,2} & a_{2,3} \end{matrix} | ≠ 0,

the usual solution

x_{2} = \begin{aligned}& | & \begin{matrix}b_{1} & a_{1,3} \\ b_{2} & a_{2,3} \end{matrix} & | \\ | & & \begin{matrix}a_{1,2} & a_{1,3} \\ a_{2,2} & a_{2,3} \end{matrix} & & | \end{aligned} − \begin{matrix}| & \begin{matrix}a_{1,1} & a_{1,3} \\ a_{2,1} & a_{2,3} \end{matrix} & | \\ | & \begin{matrix}a_{1,2} & a_{1,3} \\ a_{2,2} & a_{2,3} \end{matrix} & | \end{matrix} x_{1}, x_{3} = \begin{aligned}& | & \begin{matrix}a_{1,2} & b_{1} \\ a_{2,2} & b_{2} \end{matrix} & | \\ | & & \begin{matrix}a_{1,2} & a_{1,3} \\ a_{2,2} & a_{2,3} \end{matrix} & & | \end{aligned} − \begin{matrix}| & \begin{matrix}a_{1,2} & a_{1,1} \\ a_{2,2} & a_{2,1} \end{matrix} & | \\ | & \begin{matrix}a_{1,2} & a_{1,3} \\ a_{2,2} & a_{2,3} \end{matrix} & | \end{matrix} x_{1}

is obtained by reparametrizing the obtained rational curve through the simplification of the rational functions in (27) which provides x_{2} and x_{3} in terms of x_{1} after performing the corresponding polynomial division with respect to t.

3.2 Cramer’s Rule for overdetermined systems of linear equations

For the overdetermined system of linear equations,

( \begin{matrix}a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2} \\ a_{3,1} & a_{3,2} \end{matrix} ) ( \begin{matrix}x_{1} \\ x_{2} \end{matrix} ) = ( \begin{matrix}b_{1} \\ b_{2} \\ b_{3} \end{matrix} ) ,  (28)

the Generalized Gram’s Polynomials are given by det(I_{3} + zA A^{∘}):

\begin{aligned}1 & + (a_{3,1}^{2}t^{2} + (a_{3,2}^{2} + a_{2,1}^{2}) t + (a_{2,2}^{2} + a_{1,1}^{2}) + \frac{a_{1,2}^{2}}{t} ) z \\ & +( | \begin{matrix}a_{2,1} & a_{2,2} \\ a_{3,1} & a_{3,2} \end{matrix} |^{2} t^{2} + | \begin{matrix}a_{1,1} & a_{1,2} \\ a_{3,1} & a_{3,2} \end{matrix} |^{2} t + | \begin{matrix}a_{1,1} & a_{1,2} \\ a_{2,1} & a_{2,2} \end{matrix} |^{2} )z^{2}. \end{aligned}

Under the assumption of rank 2 for the matrix A, the following curve (in 𝕂^{2}) of solutions is obtained:

x_{1}(t) = \frac{| \begin{matrix}a_{2,1} a_{2,2} \\ a_{3,1} a_{3,2} \end{matrix} | | \begin{matrix}b_{2} a_{2,2} \\ b_{3} a_{3,2} \end{matrix} | t^{2} + | \begin{matrix}a_{1,1} a_{1,2} \\ a_{3,1} a_{3,2} \end{matrix} | | \begin{matrix}b_{1} a_{1,2} \\ b_{3} a_{3,2} \end{matrix} | t + | \begin{matrix}a_{1,1} a_{1,2} \\ a_{2,1} a_{2,2} \end{matrix} | | \begin{matrix}b_{1} a_{1,2} \\ b_{3} a_{2,2} \end{matrix} |}{| \begin{matrix}a_{2,1} a_{2,2} \\ a_{3,1} a_{3,2} \end{matrix} |^{2} t^{2} + | \begin{matrix}a_{1,1} a_{1,2} \\ a_{3,1} a_{3,2} \end{matrix} |^{2} t + | \begin{matrix}a_{1,1} a_{1,2} \\ a_{2,1} a_{2,2} \end{matrix} |^{2}},

x_{2}(t) = \frac{| \begin{matrix}a_{2,1} a_{2,2} \\ a_{3,1} a_{3,2} \end{matrix} | | \begin{matrix}a_{2,1} b_{2} \\ a_{3,1} b_{3} \end{matrix} | t^{2} + | \begin{matrix}a_{1,1} a_{1,2} \\ a_{3,1} a_{3,2} \end{matrix} | | \begin{matrix}a_{1,1} b_{1} \\ a_{3,1} b_{3} \end{matrix} | t + | \begin{matrix}a_{1,1} a_{1,2} \\ a_{2,1} a_{2,2} \end{matrix} | | \begin{matrix}a_{1,1} b_{1} \\ a_{2,1} b_{2} \end{matrix} |}{| \begin{matrix}a_{2,1} a_{2,2} \\ a_{3,1} a_{3,2} \end{matrix} |^{2} t^{2} + | \begin{matrix}a_{1,1} a_{1,2} \\ a_{3,1} a_{3,2} \end{matrix} |^{2} t + | \begin{matrix}a_{1,1} a_{1,2} \\ a_{2,1} a_{2,2} \end{matrix} |^{2}}  (29)

In this case, where the existence of solution is not assured, the evaluation of A does not provide the the vector b. Instead, the conditions for the existence of solution are obtained:

( \begin{matrix}a_{1,1} a_{1,2} \\ a_{2,1} a_{2,2} \\ a_{3,1} a_{3,2} \end{matrix} ) ( \begin{matrix}x_{1}(t) \\ x_{2}(t) \end{matrix} ) = ( \begin{matrix}b_{1} \\ b_{2} \\ b_{3} \end{matrix} ) − \frac{| \begin{matrix}a_{1,1} a_{1,2} b_{1} \\ a_{2,1} a_{2,2} b_{2} \\ a_{3,1} a_{3,2} b_{3} \end{matrix} | ( \begin{matrix}| \begin{matrix}a_{2,1} a_{2,2} \\ a_{3,1} a_{3,2} \end{matrix} | t^{2} \\ | \begin{matrix}a_{1,1} a_{1,2} \\ a_{3,1} a_{3,2} \end{matrix} | t \\ | & \begin{matrix}a_{1,1} a_{1,2} \\ a_{2,1} a_{2,2} \end{matrix} & | \end{matrix} )}{| \begin{matrix}a_{2,1} a_{2,2} \\ a_{3,1} a_{3,2} \end{matrix} |^{2} t^{2} + | \begin{matrix}a_{1,1} a_{1,2} \\ a_{3,1} a_{3,2} \end{matrix} |^{2} t + | \begin{matrix}a_{1,1} a_{1,2} \\ a_{2,1} a_{2,2} \end{matrix} |^{2}}  (30)

The solution curve contains a true solution of the considered system (under the assumption of rank 2) if and only if, as expected,

| \begin{matrix}a_{1,1} & a_{1,2} & b_{1} \\ a_{2,1} & a_{2,2} & b_{2} \\ a_{3,1} & a_{3,2} & b_{3} \end{matrix} | = 0.

Under this condition (and assumption of rank 2 for A) the solution curve in (29) reduces to exactly one point since every rational function defining the solution curve simplifies to a constant: depending on which maximal minor provides the rank 2 for A, a different constant is obtained for each rational function after the corresponding simplification.

3.3 Parametric solving of systems of linear equations

If the matrix A depends on some parameters then this method provides a nice way to parameterize its rank and the solutions of any system of linear equations A x = v by using the coefficients of the characteristic polynomial A A^{∘}.

Example : We consider a linear system defined over ℂ, where the coefficient matrix A is given by:

( \begin{matrix}4ba + 4a^{2} + 4b^{2} + 4 & 7 − 2a^{2} − 2b^{3} & 7a − 2a^{3} − 2ab^{3} + 3 \\ 4ba^{2} + 4a^{3} + 4ab^{2} + 4a+ & 7a − 2a^{3} − 2ab^{3} + 5a^{2}+ & 7a^{2} − 2a^{4} − 2a^{2}b^{3} − 6a+ \\ +2ba + 2a^{2} + 2b^{2} + 2 & +5b^{3} − 9 & +5a^{3} + 5ab^{3} + 1 \\ 8ba + 8a^{2} + 8b^{2} + 8 & 2 + a^{2} + b^{3} & 2a + a^{3} + ab^{3} + 4 \\ 4ba + 4a^{2} + 4b^{2} + 4 & 3 − a^{2} − b^{3} & 3a − a^{3} − ab^{3} + 1 \\ −6ba − 6a^{2} − 6b^{2} − 6 & 2 − 2a^{2} − 2b^{3} & 2a − 2a^{3} − 2ab^{3} − 2 \end{matrix} )

and a, b are parameters taking values in ℂ. Observe that by applying our method, it is not necessary to consider the conjugates of the parameters appearing in the system.

We first calculate the Generalized Gram’s Polynomials in order to study the different possible ranks of A according to a and b. The matrix A^{∘} is given by:

A^{∘} = Q_{3}^{−1} A^{t} Q_{5} = ( \begin{matrix}1 & 0 & 0 \\ 0 & t^{−1} & 0 \\ 0 & 0 & t^{−2} \end{matrix} ) A^{t} ( \begin{matrix}1 & 0 & 0 & 0 & 0 \\ 0 & t & 0 & 0 & 0 \\ 0 & 0 & t^{2} & 0 & 0 \\ 0 & 0 & 0 & t^{3} & 0 \\ 0 & 0 & 0 & 0 & t^{4} \end{matrix} ) .

Thus, det(I_{5} + z AA^{∘}) = 1 + a_{1}(t)z + a_{2}(t)z^{2} + a_{3}(t)z^{3}. In this case a_{1}(t) is never the zero polynomial. Moreover, with

a_{3}(t) = a_{3,6} t^{6} + a_{3,5} t^{5} + a_{3,4} t^{4} + … + a_{3,0},
a_{2}(t) = a_{2,8} t^{6} + a_{2,7} t^{5} + … + a_{2,0}t^{−2},

by Equation (20), Gram’s Coefficients for k ∈ {3, 2} are given by:

a_{3, l} : \{ \begin{matrix}a_{3,0} = μ_{\{1,2,3\},\{1,2,3\}}^{2}, a_{3,1} = μ_{\{1,2,4\},\{1,2,3\}}^{2}, \\ a_{3,2} = μ_{\{1,2,5\},\{1,2,3\}}^{2} + μ_{\{1,3,4\},\{1,2,3\}}^{2}, \\ a_{3,3} = μ_{\{1,3,5\},\{1,2,3\}}^{2} + μ_{\{2,3,4\},\{1,2,3\}}^{2}, \\ a_{3,4} = μ_{\{2,3,5\},\{1,2,3\}}^{2} + μ_{\{1,4,5\},\{1,2,3\}}^{2}, \\ a_{3,5} = μ_{\{2,4,5\},\{1,2,3\}}^{2}, a_{3,6} = μ_{\{3,4,5\},\{1,2,3\}}^{2}, \end{matrix}

a_{2, l} : \{ \begin{matrix}a_{2,0} = μ_{\{1,2\},\{2,3\}}^{2}, a_{2,1} = μ_{\{1,2\},\{1,3\}}^{2} + μ_{\{1,3\},\{2,3\}}^{2} \\ a_{2,2} = μ_{\{1,2\},\{1,2\}}^{2} + μ_{\{1,3\},\{1,3\}}^{2} + μ_{\{2,3\},\{2,3\}}^{2} + μ_{\{1,4\},\{2,3\}}^{2}, \\ a_{2,3} = μ_{\{1,3\},\{1,2\}}^{2} + μ_{\{1,4\},\{1,3\}}^{2} + μ_{\{2,3\},\{1,3\}}^{2} + μ_{\{1,5\},\{2,3\}}^{2} + μ_{\{2,4\},\{2,3\}}^{2}, \\ a_{2,4} = μ_{\{1,4\},\{1,2\}}^{2} + μ_{\{2,3\},\{1,2\}}^{2} + μ_{\{1,5\},\{1,3\}}^{2} + μ_{\{2,4\},\{1,3\}}^{2}+ \\ +μ_{\{2,5\},\{2,3\}}^{2} + μ_{\{3,4\},\{2,3\}}^{2}, \\ a_{2,5} = μ_{\{1,5\},\{1,2\}}^{2} + μ_{\{2,4\},\{1,2\}}^{2} + μ_{\{3,4\},\{1,3\}}^{2} + μ_{\{3,5\},\{2,3\}}^{2} + μ_{\{2,5\},\{1,3\}}^{2}, \\ a_{2,6} = μ_{\{2,5\},\{1,2\}}^{2} + μ_{\{3,4\},\{1,2\}}^{2} + μ_{\{3,5\},\{1,3\}}^{2} + μ_{\{4,5\},\{2,3\}}^{2}, \\ a_{2,7} = μ_{\{3,5\},\{1,2\}}^{2} + μ_{\{4,5\},\{1,3\}}^{2}, a_{2,8} = μ_{\{4,5\},\{1,2\}}^{2} \end{matrix}

and the different possible ranks of A according to the values of the Generalized Gram’s Polynomials are:

1. a_{3}(t) ≠ 0 ⟺ (a^{2} + b^{3} − 2)(a^{2} + 1 + ba + b^{2}) ≠ 0 ⟺ rk(A) = 3

2. a_{3}(t) = 0 ∧ a_{2}(t) ≠ 0 ⟺ rk(A) = 2:

• (a^{2} + b^{3} − 2) = 0, (a^{2} + 1 + ba + b^{2}) ≠ 0

• (a^{2} + 1 + ba + b^{2}) = 0, (a^{2} + b^{3} − 2) ≠ 0

3. a_{3}(t) = 0 ∧ a_{2}(t) = 0 ⟺ rk(A) = 1

• a^{6} + 2a^{5} + 4a^{4} − a^{3} − a^{2} − 6a + 5 = 0, b − a^{2} + 2 − a^{3} − a = 0 ⇔ (a^{2} + b^{3} − 2) = 0 ∧ (a^{2} + 1 + ba + b^{2}) = 0

Once the rank is determined, in view of Equations (18) and (19), the different possible solutions of the linear system are uniformly given by:

• rk(A) = 3: \overline{x} = \frac{1}{a_{3}(t)} ((A^{∘}A)^{2} − a_{1}(t)A^{∘}A + a_{2}(t)) A^{∘}v

• rk(A) = 2:

\overline{x} = \frac{1}{a_{2}(t)}(−A^{∘}A + a_{1}(t)I_{3})A^{∘}v  (31)

• rk(A) = 1 : \overline{x} = \frac{1}{a_{1}(t)}A^{∘}v

For instance, if we consider a = 1, b = 1, v = (−6, −8, −8, −2, 4), then rk(A)= rk(A|v)=2 and the solution is given by Equation (31) as follows:

\overline{x} = (0, \frac{−2t}{t + 4}, \frac{−4}{t + 4}) = (0, −2, 0) + \frac{1}{t + 4}(0, 8, −4),

such that (0, −2, 0) is a concrete zero of our system and \frac{1}{t+4}(0, 8, −4) is solution of the homogenous linear system defined by A. ⊓ ⊔ Example : We consider a linear system defined over ℤ_{11}, where the coefficient matrix A is given by:

( \begin{matrix}7ab + 2a^{2}b + 9a^{2} + 2a^{3} + 7a & 7a + 1 + 9ab + 9b & 3 \\ 2a^{3}b + 7a^{2}b + 2a^{4} + 9a^{3} + 8a^{2}+ & 6a^{2} + 3a + 9a^{2}b + 3ab+ & 2a \\ +ab + 9b + 10a + 9 & +5b + 1 \\ 7ab + 2a^{2}b + 9a^{2} + 2a^{3} + 7a & 2a + 5 + ab + b & 4 \\ a^{2}b + 9ab + a^{3} + 10a^{2} + 9a & 3a^{2} + 4 + ab + b & 5 + 3a \\ 9ab + a^{3} + 2a^{2} + a + 3a^{3}b + 10b+ & 3a + 7 + 7ab + 3a^{2}+ & 3 + a + 4b \\ +a^{4} + 10 + 7ab^{2} + 2a^{2}b^{2} + 9a^{2}b & +10a^{2}b + ab^{2} + b^{2} \end{matrix} )

and a, b are parameters taking values in ℤ_{11}.

We first calculate the Generalized Gram’s Polynomials in order to study the different possible ranks of A according to a and b. The matrix A^{∘} is given by:

A^{∘} = Q_{3}^{−1} A^{t} Q_{5} = ( \begin{matrix}1 & 0 & 0 \\ 0 & t^{−1} & 0 \\ 0 & 0 & t^{−2} \end{matrix} ) A^{t} ( \begin{matrix}1 & 0 & 0 & 0 & 0 \\ 0 & t & 0 & 0 & 0 \\ 0 & 0 & t^{2} & 0 & 0 \\ 0 & 0 & 0 & t^{3} & 0 \\ 0 & 0 & 0 & 0 & t^{4} \end{matrix} ) .

Thus, det(I_{5} + z AA^{∘}) = 1 + a_{1}(t)z + a_{2}(t)z^{2} + a_{3}(t)z^{3}. Note that a_{1}(t) is never the zero polynomial; in fact, a_{1,0} = 9. Moreover, with

a_{3}(t) = a_{3,6}t^{6} + a_{3,5}t^{5} + a_{3,4} t^{4} + … + a_{3,0}, a_{2}(t) = a_{2,8}t^{6} + a_{2,7} t^{5} + … + a_{2,0}t^{−2},

by Equation (20), Gram’s Coefficients for k ∈ {3, 2} are given by:

a_{3, l} : \{ \begin{matrix}a_{3,0} = μ_{\{1,2,3\},\{1,2,3\}}^{2}, a_{3,1} = μ_{\{1,2,4\},\{1,2,3\}}^{2}, \\ a_{3,2} = μ_{\{1,2,5\},\{1,2,3\}}^{2} + μ_{\{1,3,4\},\{1,2,3\}}^{2}, \\ a_{3,3} = μ_{\{1,3,5\},\{1,2,3\}}^{2} + μ_{\{2,3,4\},\{1,2,3\}}^{2}, \\ a_{3,4} = μ_{\{2,3,5\},\{1,2,3\}}^{2} + μ_{\{1,4,5\},\{1,2,3\}}^{2}, \\ a_{3,5} = μ_{\{2,4,5\},\{1,2,3\}}^{2}, a_{3,6} = μ_{\{3,4,5\},\{1,2,3\}}^{2}, \end{matrix}

a_{2, l} : \{ \begin{matrix}a_{2,0} = μ_{\{1,2\},\{2,3\}}^{2}, a_{2,1} = μ_{\{1,2\},\{1,3\}}^{2} + μ_{\{1,3\},\{2,3\}}^{2} \\ a_{2,2} = μ_{\{1,2\},\{1,2\}}^{2} + μ_{\{1,3\},\{1,3\}}^{2} + μ_{\{2,3\},\{2,3\}}^{2} + μ_{\{1,4\},\{2,3\}}^{2}, \\ a_{2,3} = μ_{\{1,3\},\{1,2\}}^{2} + μ_{\{1,4\},\{1,3\}}^{2} + μ_{\{2,3\},\{1,3\}}^{2} + μ_{\{1,5\},\{2,3\}}^{2} + μ_{\{2,4\},\{2,3\}}^{2}, \\ a_{2,4} = μ_{\{1,4\},\{1,2\}}^{2} + μ_{\{2,3\},\{1,2\}}^{2} + μ_{\{1,5\},\{1,3\}}^{2} + μ_{\{2,4\},\{1,3\}}^{2}+ \\ +μ_{\{2,5\},\{2,3\}}^{2} + μ_{\{3,4\},\{2,3\}}^{2}, \\ a_{2,5} = μ_{\{1,5\},\{1,2\}}^{2} + μ_{\{2,4\},\{1,2\}}^{2} + μ_{\{3,4\},\{1,3\}}^{2} + μ_{\{3,5\},\{2,3\}}^{2} + μ_{\{2,5\},\{1,3\}}^{2}, \\ a_{2,6} = μ_{\{2,5\},\{1,2\}}^{2} + μ_{\{3,4\},\{1,2\}}^{2} + μ_{\{3,5\},\{1,3\}}^{2} + μ_{\{4,5\},\{2,3\}}^{2}, \\ a_{2,7} = μ_{\{3,5\},\{1,2\}}^{2} + μ_{\{4,5\},\{1,3\}}^{2}, a_{2,8} = μ_{\{4,5\},\{1,2\}}^{2} \end{matrix}

and the different possible ranks of A according to the values of the Generalized Gram’s Polynomials are:

1. a_{3}(t) ≠ 0 ⟺ (a + b + 1)(b − 2)(a − 10)(a − 2) ≠ 0 ⟺ rk(A) = 3

2. a_{3}(t) = 0 ∧ a_{2}(t) ≠ 0 ⟺ rk(A) = 2:

• a = 2, b ≠ 2

• b = 2, (a − 2)(a − 8) ≠ 0

• a = 10, b ≠ 0

• a + b + 1 = 0, b(b − 2) ≠ 0

3. a_{3}(t) = 0 ∧ a_{2}(t) = 0 ⟺ rk(A) = 1

• a = 2, b = 2

• a = 8, b = 2

• a = 10, b = 0

Once the rank is determined, in view of Equations (18) and (19), the different possible solutions of the linear system are uniformly given by:

• rk(A) = 3: \overline{x} = \frac{1}{a_{3}(t)} ((A^{∘}A)^{2} − a_{1}(t)A^{∘}A + a_{2}(t)) A^{∘}v

• rk(A) = 2:

\overline{x} = \frac{1}{a_{2}(t)}(−A^{∘}A + a_{1}(t)I_{3})A^{∘}v  (32)

• rk(A) = 1 : \overline{x} = \frac{1}{a_{1}(t)}A^{∘}v

For instance, if we consider a = 3, b = 2, v = (9, 5, 0, 2, 6), then rk(A) = rk(A|v) = 2 and the solution is given by Equation (32) as follows:

\overline{x} = (1, \frac{t}{t + 3}, \frac{6}{t + 3}) = (1, 1, 0) + \frac{1}{t + 3}(0, 8, 6),

such that (1, 1, 0) is a concrete zero of our system and \frac{1}{t+3}(0, 8, 6) is solution of the homogenous linear system defined by A. ⊓ ⊔

References

[1] C. Ballarin and M. Kauers: Solving parametric linear systems: an experiment with constraint algebraic programming. SIGSAM Bull. 38, 33–46, 2004.

[2] R. K. Bhaskara: The Theory of Generalized Inverses over a Commutative Ring. Taylor & Francis. Londres, 2002.

[3] D. Bini and V. Y. Pan: Polynomial and matrix computations. Progress in Theoretical Computer Science, Birkhäuser, 1994.

[4] A. Borodin, J. von zur Gathen and J. Hopcroft: Fast parallel matrix and GCD computations. Information and Control 52, 241–256, 1982.

[5] R. Dautray and J.–L. Lions: Mathematical Analysis and Numerical Methods for Science and Technology. Springer, 1988.

[6] O. Dessombz, F. Thouverez, J. P. Lainé and L. Jézéquel: Analysis of mechanical systems using interval computations applied to finite elements methods. Journal of Sound and Vibration, 239, 5, 949–968, 2001.

[7] G. Diaz-Toca, L. Gonzalez-Vega, H. Lombardi and C. Quitté: Modules projectifs de type fini, applications linéaires croisées et inverses généralisés. Preprint, 2005.

[8] H. Fischer: Automatic differentiation of the vector that solves a parametric linear system. J. Comput. Appl. Math. 35, 169–184, 1991.

[9] G. H. Golub and Ch. F. van Loan: Matrix Computations. J. Hopkins Univ. Press, Baltimore and London. 3rd edition, 1996.

[10] D. A. Harville Matrix Algebra form a Statistician’s Perspective Springer, 2000.

[11] J. Heintz: Definability and fast quantifier elimination in algebraically closed fields. Theoret. Comput. Sci. 24, 3, 239–277, 1983.

[12] L. V. Kolev: Outer Solution of Linear Systems Whose Elements Are Affine Functions of Interval Parameters. Reliable Computing 8, 6, 493–501, 2002.

[13] K. Jensen. Coloured Petri Nets. Springer, 1996.

[14] P. Lancaster and M. Tismenetsky: The Theory of Matrices, 2/e. Academic Press, 1985.

[15] R. Muhanna and R. L. Mullen: Uncertainty in Mechanics Problems - Interval-Based Approach. Journal of Engineering Mechanics 127, 6, 557-566, 2001.

[16] K. Mulmuley: A fast parallel algorithm to compute the rank of a matrix over an arbitrary field. Combinatorica 7/1, 101–104, 1987.

[17] K. Prasad and R. Bapat: The Generalized Moore–Penrose Inverse. Linear Algebra Appl. 165, 59–69, 1992.

[18] W. Y. Sit: An algorithm for solving parametric linear systems. J. Symbolic Comput. 13, 353–394, 1992.

[19] H.–M. Winkels and M. Meika: An integration of efficiency projections into the Geoffrion approach for multiobjective linear programming. European J. Oper. Res. 16, 113–127, 1984.