Generalized Wong sequences and their applications to Edmonds' problems

Introduction

In 1967, Edmonds introduced the following problem : Given a matrix $M$ whose entries are homogeneous linear polynomials over the integers, determine the rank of $M$. The problem is the same as determining the maximum rank of a matrix in a linear space of matrices over the rationals. In this paper we consider this question and its certain variants over more general fields.

Previous works on Edmonds’ problems mostly dealt with the case when the given matrices $B_{1},\dots,B_{m}$ satisfy certain property. For example, Lovász considered several cases of SMR, including when the $B_{i}$’s are of rank $1$, and when they are skew symmetric matrices of rank $2$. These classes were then shown to have deterministic polynomial-time algorithms , see Section 1.1 for more details.

The difference between properties of matrices and properties of matrix spaces is critical for Edmonds’ problems. In particular, whether a matrix space satisfies a certain property or not, should not depend on choices of basis. We are not aware of any result on the complexity of finding rank one generators for a subspace ${\cal B}$ in $\mathbf{R_{1}}$ if it is given by a basis consisting of not necessarily rank one matrices. We believe that the problem is hard. Thus the existence of algorithms for SMR when the $B_{i}$’s are rank-$1$ does not immediately imply algorithms for matrix spaces in $\mathbf{R_{1}}$.

To ease the description of our results, we make a few definitions and notations. We denote by ${\rm rank}(B)$ the rank of a matrix $B$, and we set $\mbox{\rm corank}(B)=n-{\rm rank}(B).$ For a matrix space ${\cal B}$ we set ${\rm rank}({\cal B})=\max\{{\rm rank}(B)\mid B\in{\cal B}\}$ and $\mbox{\rm corank}({\cal B})=n-{\rm rank}({\cal B})$. We say that ${\cal B}$ is singular if ${\rm rank}({\cal B})<n$, that is if ${\cal B}$ does not contain a nonsingular element, and nonsingular otherwise.

Theorem 1 can be slightly strengthened as follows: instead of assuming that the whole space ${\cal B}$ is rank-$1$ spanned, it is sufficient to suppose that a subspace of ${\cal B}$ of co-dimension one is spanned by rank-$1$ matrices. See Remark 15 (2) for the work needed to achieve this.

Let us comment briefly on the framework for our algorithms. We generalize the first and second Wong sequences for matrix pencils (essentially two-dimensional matrix spaces) which have turned out to be useful among others in the area of linear differential-algebraic equations (see the recent survey ). These were originally defined in for a pair of matrices $(A,B)$, and were recently used to compute the Kronecker normal form in a numerical stable way . We generalize Wong sequences to the case $({\cal A},{\cal B})$ where ${\cal A}$ and ${\cal B}$ are matrix spaces, and show that they have analogous basic properties to the original ones. We relate the generalized Wong sequences to Edmonds’ problems via singularity witnesses. Essentially this connection allows us to design the algorithm for $\mathbf{R_{1}}$ using the second Wong sequence, and the algorithm for $\mathbf{UT}$ using the first Wong sequence. We remark that the application of the second Wong sequence is not new. Similar techniques were used in to find maximum rank matrices in the case where rank one generators for ${\cal B}$ were given. Furthermore, while preparing the present version, we became aware of the paper by Fortin and Reutenauer in which essentially the same method is used for testing existence of $\mbox{\rm corank}({\cal B})$-singularity witnesses (on a randomized algebraic RAM).

Over fields of constant size, the SMR has certain practical implications , but is shown to be NP-hard in general. Some special cases have been studied, mostly in the form of the mixed matrices, that is linear matrices where each entry is either a variable or a field element. Then by restricting the way variables appear in the matrices some cases turn out to have efficient deterministic algorithms, including when every variable appears at most once (, building on ), and when the mixed matrix is skew-symmetric and every variable appears at most twice (). Finally in , Ivanyos, Karpinski and Saxena present a deterministic polynomial-time algorithm for the case when among the input matrices $B_{1},\dots,B_{m}$ all but $B_{1}$ are of rank $1$.

As a computational model of polynomials, determinants with affine polynomial entries turn out to be equivalent to algebraic branching programs (ABPs) up to a polynomial overhead. Thus the identity test for ABPs is the same as SDIT. For restricted classes of ABPs, (quasi)polynomial-time deterministic identity test algorithms have been devised (cf. and the references therein). Note that identity test results for SDIT and ABPs are in general incomparable. For an application of SDIT to quantum information processing see .

In Section 2 we define Wong sequences of a pair of matrix spaces, and present their basic properties. In Section 3 the connection between the second Wong sequence and singularity witnesses is shown. Based on this connection we introduce the power overflow problem, and reduce the SMR to it. We also prove here Theorem 1 under the hypothesis that there is a polynomial time algorithm for the power overflow problem. In Section 4 we show an algorithm for the power overflow problem that works in polynomial time for rank-$1$ spanned matrix spaces. Section 5 is devoted to the algorithm for triangularizable matrix spaces, proving Theorem 2. Finally, in Section 6 we propose and investigate some natural subclasses of the Edmonds-Rado class.

Wong sequences for pairs of matrix spaces

Let $U\leq V$ and $W\leq V^{\prime}$ be subspaces of $V$ and $V^{\prime}$, respectively. For $A\in{\rm Lin}(V,V^{\prime})$, the image of $U$ under $A$ is $A(U)=\{A(u)\mid u\in U\}$, and the preimage of $W$ under $A$ is $A^{-1}(W)=\{v\in V\mid A(v)\in W\}$. To define generalized Wong sequences, the first step is to generalize the definitions of image and preimage under a single linear map $A$, to those under a matrix space ${\cal A}\leq{\rm Lin}(V,V^{\prime})$.

Naturally, the image of $U$ under ${\cal A}$ is the span of the images of $U$ under every $A\in{\cal A}$, that is ${\cal A}(U)=\langle\cup_{A\in{\cal A}}A(U)\rangle=\langle\{A(u)\mid A\in{\cal A},u\in U\}\rangle.$ On the other hand, the preimage of $W$ under ${\cal A}$ may be somewhat unexpected. It turns out that we need to take the intersection of the preimages of $W$ under every $A\in{\cal A}$, that is ${\cal A}^{-1}(W)=\cap_{A\in{\cal A}}A^{-1}(W)=\{v\in V\mid\forall A\in{\cal A},A(v)\in W\}$. Note that ${\cal A}(U)$ (resp. ${\cal A}^{-1}(W)$) is a subspace of $V^{\prime}$ (resp. $V$). Moreover, if ${\cal A}$ is spanned by $\{A_{1},\dots,A_{m}\}$, then ${\cal A}(U)=\langle\cup_{i\in[m]}A_{i}(U)\rangle$, and ${\cal A}^{-1}(W)=\cap_{i\in[m]}A_{i}^{-1}(W)$. Some easy and useful facts are the following.

For ${\cal A},{\cal B}\leq{\rm Lin}(V,V^{\prime})$, and $U,S\leq V$, $W,T\leq V^{\prime}$, we have:

If $U\subseteq S$ and $W\subseteq T$, then ${\cal A}(U)\subseteq{\cal A}(S)$ and ${\cal A}^{-1}(W)\subseteq{\cal A}^{-1}(T)$;

If ${\cal B}(U)\subseteq{\cal A}(U)$ and ${\cal B}(S)\subseteq{\cal A}(S)$, then ${\cal B}(\langle U\cup S\rangle)\subseteq{\cal A}(\langle U\cup S\rangle)$;

If ${\cal B}^{-1}(W)\supseteq{\cal A}^{-1}(W)$ and ${\cal B}^{-1}(T)\supseteq{\cal A}^{-1}(T)$, then ${\cal B}^{-1}(W\cap T)\supseteq{\cal A}^{-1}(W\cap T)$;

${\cal A}^{-1}({\cal A}(U))\supseteq U$, and ${\cal A}({\cal A}^{-1}(W))\subseteq W$.

We now define two Wong sequences for a pair of matrix subspaces.

When ${\cal A}=\langle A\rangle$ and ${\cal B}=\langle B\rangle$ are one dimensional matrix spaces, the Wong sequences for $({\cal A},{\cal B})$ coincide with the classical Wong sequences for the matrix pencil $Ax-B$ . The following properties are straightforward generalizations of those for classical Wong sequences. We start by considering the first Wong sequence.

Suppose now that ${\cal B}(U_{i})\subseteq{\cal A}(U_{i})$, for some $i$. Then $U_{i}\subseteq{\cal B}^{-1}({\cal B}(U_{i}))\subseteq{\cal B}^{-1}({\cal A}(U_{i}))$ respectively by Lemma 3 (4) and (1), which gives $U_{i+1}=U_{i}$. If ${\cal B}(U_{i})\not\subseteq{\cal A}(U_{i})$ then there exist $B\in{\cal B}$ and $v\in U_{i}$ such that $B(v)\not\in{\cal A}(U_{i})$. Thus $v\not\in{\cal B}^{-1}({\cal A}(U_{i}))=U_{i+1}$, which gives $U_{i+1}\subset U_{i}$. ∎

$U^{*}$ is the largest subspace $T\leq V$ such that ${\cal B}(T)\subseteq{\cal A}(T)$.

By Proposition 5 we know that $U^{*}$ satisfies ${\cal B}(U^{*})\subseteq{\cal A}(U^{*})$. Consider an arbitrary $T\leq V$ such that ${\cal B}(T)\subseteq{\cal A}(T)$, we show by induction that $T\subseteq U_{i}$, for all $i$. When $i=0$ this trivially holds. Suppose that $T\subseteq U_{i}$, for some $i$. Then by repeated applications of Lemma 3 we have $T\subseteq{\cal B}^{-1}({\cal B}(T))\subseteq{\cal B}^{-1}({\cal A}(T))\subseteq{\cal B}^{-1}({\cal A}(U_{i}))=U_{i+1}$. ∎

The limit subspace $W^{*}$ is the smallest subspace $T\leq V^{\prime}$ s.t. ${\cal B}^{-1}(T)\supseteq{\cal A}^{-1}(T)$.

Wong sequences can be computed in time using $(n+n^{\prime})^{O(1)}$ on an algebraic RAM.

The second Wong sequence and rank-111 spanned matrix spaces

Let us now suppose that some $U\leq V$ is a $\mbox{\rm corank}(A)$-singularity witness, that is $\dim(U)-\dim({\cal B}(U))\geq\mbox{\rm corank}(A)$. Then $\dim(U)-\dim(A(U))\geq\mbox{\rm corank}(A)$ because $A\in{\cal B}$. Since the reverse inequality always holds without any condition on $U$, we have $\dim(U)-\dim(A(U))=\mbox{\rm corank}(A)$. Similarly we have $\dim(U)-\dim({\cal B}(U))=\mbox{\rm corank}(A)$, which implies that $\dim(A(U))=\dim({\cal B}(U))$, and therefore $A(U)={\cal B}(U)$. For a subspace $S\leq V$ the equality $\dim(S)-\dim(A(S))=\mbox{\rm corank}(S)$ is equivalent to $\ker(A)\subseteq S$, thus we have $\ker(A)\subseteq U$ from which it follows that $U=A^{-1}(A(U))$. But then ${\cal B}^{-1}(A(U))={\cal B}^{-1}({\cal B}(U))\supseteq U=A^{-1}(A(U))$. Since $W^{*}$ is the smallest subspace $T\leq V^{\prime}$ satisfying ${\cal B}^{-1}(T)\supseteq A^{-1}(T)$, we can conclude that $W^{*}\subseteq A(U)$.

We remark that in , a slightly different version of this statement is proved. We decided to keep our original proof for completeness. In our terminology, Theorem 3 of states that the existence of a $\mbox{\rm corank}(A)$-singularity witness is equivalent to the equality $\dim(A^{-1}(W^{*}))=\dim(W^{*})+\dim(\ker(A))$. Both versions offer a straightforward method for testing existence of (and computing) $\mbox{\rm corank}(A)$-singularity witnesses. Besides that our version resembles the concept of augmenting paths in algorithms for matchings in bipartite graphs, it offers the possibility of stopping the construction of the Wong sequence at the point after which (while working over the rationals) data blowup can occur; this data blowup can occur if we adopt the naive way of computing the preimage of a subspace under $A$. Before that point, we will make use of a pseudo-inverse of $A$. We describe now this method.

Let $n=\dim(V)$ and $n^{\prime}=\dim(V^{\prime})$. First of all we assume without loss of generality that $n=n^{\prime}$. Indeed, if $n<n^{\prime}$ we can add as a direct complement a suitable space to $V$ on which ${\cal B}$ acts as zero, and if $n>n^{\prime}$, we can embed $V^{\prime}$ into a larger space. In terms of matrices, this means augmenting the elements of ${\cal B}$ by zero columns or zero rows to obtain square matrices. This procedure affects neither the ranks of the matrices in ${\cal B}$ nor the singularity witnesses.

If we find that the condition holds then $A^{\prime}(W^{*})$ by Lemma 9 is a $\mbox{\rm corank}({\cal B})$-singularity witness, and it can be easily computed from $W^{*}$. ∎

2 The power overflow problem

Combining Lemma 10 and Fact 11 we get also an equivalent condition for $A$ being of maximum rank.

This lemma leads us to reduce the problems of deciding if $A$ is of the maximum rank, and finding a matrix of rank larger than $A$ when this is not the case, to the following question.

Using this result whose proof is given in Section 4 we are now ready to prove Theorem 1.

The power overflow problem for rank-111 spanned matrix spaces

The following lemma explains why ${\cal H}_{i}$’s are useful for the purpose of powerflow problem.

In general, ${\cal H}_{i}$ can be . In our setting, due to the existence of a basis of rank-$1$ matrices, fortunately this is far from the case.

Finally, we introduce the following slight extension of Lemma 17 for special subspaces $U,U^{\prime}$, as applicable to Remark 15 (2).

Identical with the proof of Lemma 17, based on the observation that a projection with the prescribed properties can be deleted from any product mapping $U$ outside $U^{\prime}$. ∎

The first Wong sequence and triangularizable matrix spaces

To tackle the triangularizable matrix spaces, our starting point is the following lemma, which connects first Wong sequences with singularity witnesses.

If $\dim(U^{*})>\dim({\cal B}(U^{*}))$ then $U^{*}$ is a singularity witness. If $\dim(U^{*})=\dim({\cal B}(U^{*}))$ then the choice of $P$ and $Q$ corresponds to an appropriate basis change transformation. To see that ${\cal B}$ is nonsingular in the $X$-block, note that $A\in{\cal B}$ and $A(U^{*})={\cal B}(U^{*})$. ∎

Lemma 19 suggests a recursive algorithm: take an arbitrary $A\in{\cal B}$ and compute $U^{*}$, the limit of the first Wong sequence of $(A,{\cal B})$. If we get a singularity witness, we are done. Otherwise, if $U^{*}\neq 0$, as the $X$-block is already nonsingular, we only need to focus on the nonsingularity of $Z$-block which is of smaller size. To make this idea work, we have to satisfy essentially two conditions. We must find some $A$ such that $U^{*}\neq 0$, and to allow for recursion the specific property of the matrix space ${\cal B}$ we are concerned with has to be inherited by the subspace corresponding to the $Z$-block. It turns out that in the triangularizable case these two problems can be taken care of by the following lemma.

2. First we recall that for a vector space $V$ of dimension $n$, a complete flag of $V$ is a nested sequence of subspaces $0=V_{0}\subset V_{1}\subset\dots\subset V_{n}=V$. For ${\cal A}\leq{\rm Lin}(V,V^{\prime})$ with $\dim(V)=\dim(V^{\prime})=n$, the matrix space ${\cal A}$ is triangularizable if and only if $\exists$ complete flags $0=V_{0}\subset V_{1}\subset\dots\subset V_{n}=V$ and $0=V_{0}^{\prime}\subset V_{1}^{\prime}\subset\dots\subset V_{n}^{\prime}=V^{\prime}$ s.t. ${\cal A}(V_{i})\subseteq V_{i}^{\prime}$ for $i\in[n]$.

2 An algorithm on an algebraic RAM

Given the preparation of Lemma 20, here is the outline of an algorithm using polynomially many arithmetic operations. The algorithm recurses on the size of the matrices, with the base case being the size $1$. It checks at the beginning whether $\cap_{i\in[m]}\ker(B_{i})=0$. If this is the case then it returns $\cap_{i\in[m]}\ker(B_{i})$ which is a singularity witness. Otherwise, for all $i\in[m]$, it computes the limit $U_{i}^{*}$ of the first Wong sequence for $(B_{i},{\cal B})$. By Lemma 20 (1) there exists $j\in[m]$ such that $U_{j}^{*}\neq 0$ and $B_{j}(U)={\cal B}(U)$. The algorithm then recurses on the induced actions $B_{i}^{*}$’s of $B_{i}$’s, which are also triangularizable by Lemma 20 (2). When ${\cal B}$ is nonsingular the algorithm should return a nonsingular matrix. This nonsingular matrix is built step by step by the recursive calls, at each step we have to construct a nonsingular linear combination of $B_{j}$ and the matrix returned by the call. For this we need $n+1$ field elements.

For correctness we distinguish among the types of output of the algorithm, and show that they indeed have the required property.

This case occurs in Line 2, 4, 8 and 16. All are straightforward.

After Line 3 $\cap_{i\in[m]}\ker(B_{i})=0$. Then Lemma 20 ensures that Fail cannot be returned for triangularizable matrix spaces.

3 An algorithm over the rationals

To obtain a polynomial-time algorithm over rationals, we give first a characterization of triangularizability of a nonsingular matrix space.

$\Rightarrow$: Assume that $D^{-1}{\cal B}C$ consists of upper triangular matrices. Then $C^{-1}S^{-1}D=(D^{-1}SC)^{-1}$ is upper triangular as well, whence – as products of upper triangular matrices remain upper triangular – $D^{-1}{\cal B}S^{-1}D=(D^{-1}{\cal B}C)(C^{-1}S^{-1}D)$ also consists of upper triangular matrices. $\Leftarrow$: Assume that $D^{-1}{\cal B}S^{-1}D$ consists of upper triangular matrices. Put $C=S^{-1}D$. ∎

We have the following criterion of triangularizability:

Here $[{\cal A},{\cal A}]$ is the space spanned by the commutators $[X,Y]=XY-YX$ ($X,Y\in{\cal A}$).

With these preparations we are now ready to prove Theorem 2. Proof of Theorem 2. On an algebraic RAM Algorithm 1 is all we need. Over rationals we shall perform a reduction to finite fields via Lemma 22.

On the Edmonds-Rado class and some subclasses

There exist matrix spaces generated by projections or positive matrices outside the Edmonds-Rado class

2 Compression spaces

It is clear that when $n=n^{\prime}$, if ${\cal B}$ is a compression space then it is in the Edmonds-Rado class. The converse is not true.

There exists a matrix space in the Edmonds-Rado class which is not a compression space.

The proof of Proposition 26 relies on the following lemma, which also explains why we do not expect to achieve rank maximization for upper triangular matrices in Theorem 2.

Rank maximization of matrix spaces can be reduced to rank maximization of matrix spaces with a basis of pairwise commuting, and strictly upper triangular matrices.

3 The black-box Edmonds-Rado class

As a justification for the name of the subclass, observe that this algorithm does not make use of any properties of matrices other that their rank. It even works in the setting that instead of inputting the basis $B_{1},\ldots,B_{m}$ explicitly, we only know $m$ and have an oracle which, on input $(\alpha_{1},\ldots,\alpha_{m})$ returns the rank of $\alpha_{1}B_{1}+\ldots+\alpha_{m}B_{m}$.

While this class seems quite restrictive, it contains some interesting cases.

Concluding remarks

Our main results are deterministic polynomial time algorithms for the constructive version of Edmond’s problem (that is, finding nonsingular matrices) in certain subclasses of the Edmonds-Rado class. In the light of Gurvits’ result on the non-constructive version, probably the most interesting open problem is the deterministic complexity of the constructive version for the whole Edmonds-Rado class. Regarding the Boolean complexity of some of our algorithms, the bottleneck is our limited knowledge about the possible blowup of the sizes of bases for the Wong sequences. We are not even aware of any good bound on the size of bases for singularity witnesses (except for the rank one generated case). In particular, we do not know the Boolean complexity of finding singularity witnesses for singular triangularizable matrix spaces over the rationals.

We would like to thank the anonymous reviewers for careful reading and pointing out some gaps in an earlier version of the paper. Most of this work was conducted when G. I., Y. Q. and M. S. were at the Centre for Quantum Technologies (CQT) in Singapore, and partially funded by the Singapore Ministry of Education and the National Research Foundation, also through the Tier 3 Grant “Random numbers from quantum processes” (MOE2012-T3-1-009). Research partially supported by the European Commission IST STREP project Quantum Algorithms (QALGO) 600700, by the French ANR Blanc program under contract ANR-12-BS02-005 (RDAM project), by the Hungarian Scientific Research Fund (OTKA), and by the Hausdorff grant EXC59-1/2.

References