Deterministic Polynomial Time Algorithms for Matrix Completion Problems

Introduction

Few such cases are already known and they all look at mixed matrices, i.e. linear matrices where each entry is either a variable or a constant. Harvey et al. [HKM05], building on the works of Geelen [Gee99] and Murota [Mur00], gave an efficient deterministic algorithm for matrix completion over any field if the mixed matrix has each variable appearing at most once. While Geelen at al. [GIM03, GI05] gave an efficient deterministic algorithm when the mixed matrix is skew-symmetric and has each variable appearing at most twice.

The proof of this theorem basically involves looking at the linear space $L:=\langle B_{0},B_{1},\ldots,B_{n}\rangle$ of matrices and showing that a greedy approach can be utilized to gradually increase the rank of an element in $L$. Our methods are more algebraic and quite different from those of Lovász and Geelen. In particular our method is robust enough to check whether a given matrix in $L$ has the largest possible rank without needing the rank one generators of $L$, they are needed only if we want to increase the rank (see Section 2).

Matrix algebras or algebras of linear transformations (in this paper by an algebra we mean a linear space of matrices or linear transformations that is also closed under multiplication) play a crucial role in the algorithm for Theorem 1. We consider special instances of matrix completion problems where algebras of linear transformations arise naturally. These are certain module problems.

In the context of ${\cal S}$-modules the algebra ${\cal A}={\rm Env}(\nu({\cal S})\cup I)$ is of special interest ($I$ is the identity in ${\rm Lin}(V)$). An ${\cal S}$-submodule of $V$ is a linear subspace closed under the action of all the transformations in $\nu({\cal S})$. Obviously, the intersection of a family of submodules is again a submodule. In particular, if $T$ is a subset of $V$ then there is a smallest submodule of $V$ containing $T$: the submodule generated by $T$. It is ${\cal A}T$, the linear span of vectors obtained by application of transformations from ${\cal A}$ to vectors from $T$. The set $T\subseteq V$ is a system of generators for the ${\cal S}$-module $V$ if $V={\cal A}T$.

Cyclic submodules, i.e. those generated by a single element, are of particular interest. For $v\in V$ we consider the map $\mu_{v}:{\cal A}\rightarrow V$ given by $\mu_{v}(B)=Bv$. Obviously, $\mu_{v}$ is a linear map from ${\cal A}$ into $V$ and the set $\{\mu_{v}|v\in V\}$ is a linear space of linear maps from ${\cal A}$ to $V$. The rank of $\mu_{v}$ is the dimension of the submodule ${\cal A}v$ generated by $v$.

A “Universal” Module Problem: The matrix completion problem in this context is finding an element $v$ which generates a submodule of maximum dimension. It turns out that this problem, which we call cyclic submodule optimization, is universal in matrix completion: there is a deterministic polynomial time reduction from maximum rank matrix completion to cyclic submodule optimization (over an arbitrary base field). We show this universality in Section 3. Universality implies two hardness results. First, existence of a deterministic polynomial time algorithm for cyclic submodule optimization would imply deterministic solvability of the matrix completion problem over sufficiently large fields. Also, over small fields, cyclic submodule optimization is $NP$-hard. Second, we get analogous hardness results for the existence of injective resp. surjective homomorphisms between modules (a ${\cal S}$-module homomorphism from $V$ to $V^{\prime}$ is a linear map in ${\rm Lin}(V,V^{\prime})$ that commutes with the action of ${\cal S}$):

There is a deterministic polynomial time reduction from the existence of (resp. finding) a nonsingular matrix completion to the problem of checking for the existence of (resp. finding) a surjective (or injective) homomorphism between two modules.

This result is remarkable in view of the recent deterministic polynomial time algorithm of Brookbanks & Luks [BL08] for module isomorphism problem (see also Chistov et al. [CIK97] over special base fields).

A “Dual” Problem: In Section 4 we consider a problem which is in some sense “dual” to the cyclic submodule optimization. This is finding a system of generators of smallest size for a module. In contrast to hardness of the former problem, we have an efficient solution to the latter:

Note that the above result includes testing cyclicity of modules efficiently over any field. This problem was considered in [CIK97] over special fields as a tool for constructing isomorphisms between modules. The algorithm is based on a greedy approach analogous to the method for Theorem 1, implicitly using certain submodule dimension optimization technique for a special class of (so called semisimple) modules.

Matrix Completion with Rank One Matrices

Assume, for contradiction, that ${\rm Env}(L)\ker e$ is not contained in $eV$. Then there exists a vector $v\in\ker e$ such that $L^{s}v\not\subseteq eV$ for some integer $s$. Let $s\geq 1$ be the smallest among such integers. Then there are matrices $h_{1},\ldots,h_{s}\in L$ with $h_{s}\cdots h_{2}h_{1}v\not\in eV$ such that for every $i$, the matrix $h_{i}$ is either $e$ or has rank one. Assume that $h_{j}=e$ for some $j\leq s$. Then $j>1$ as $ev=0$. Furthermore, the minimality of $s$ implies

therefore, as $ew=w$ for every $w\in eV$, we have $h_{s}\cdots h_{j+1}h_{j}h_{j-1}\cdots h_{1}v=h_{s}\cdots$ $h_{j+1}eh_{j-1}\cdots h_{1}v=$ $h_{s}\cdots h_{j+1}h_{j-1}\cdots h_{1}v$, contradicting the minimality of $s$. Thus all the matrices $h_{1},\ldots,h_{s}$ are of rank one. Set $v_{0}=v$ and for $1\leq i\leq s$, $v_{i}=h_{i}v_{i-1}$. The minimality of $s$ implies that for every $1\leq i\leq s$ we have $v_{i}\in L^{i}v\setminus\sum_{j=0}^{i-1}L^{j}v$. In particular, the vectors $v_{0},\ldots,v_{s}$ are linearly independent. Since $h_{i}$ is a rank one transformation on $V$,

From this, and from the minimality of $s$ we infer $h_{j}v_{i-1}=0$ for every $1\leq i<j\leq s$ (otherwise $v_{j}\in h_{j}L^{i-1}v\subseteq L^{i}v$). We show below that $a:=e+h_{1}+\ldots+h_{s}$ is of a rank higher than $e$, leading to the desired contradiction.

In the proof above, the special case $s=1$ deserves special attention. In that case we have a simple method for increasing the rank over sufficiently large fields which works even without any assumption on the presence of rank one matrices. We will use this simple observation later in Section 4.

We state below a simple fact about the linear spaces of matrices that is useful in providing a certificate for the rank maximality of a given matrix.

For any subspace $W\leq U$ pick a direct complement $W^{\prime}$ of $W$ in $U$. Now $\dim U-{\rm rk\;}h$ $=\dim U-\dim hU$ $\geq(\dim W-\dim hW)+(\dim W^{\prime}-\dim hW^{\prime})$ $\geq\dim W-\dim LW$. $\Box$

Using Edmonds’ Matroid Intersection Theorem, Lovász (Section 3, [Lov89]) has shown that equality holds provided that $h$ is of maximum rank and if $L$ is spanned by rank one matrices. We give the following algorithmic generalization to the case when $L$ is spanned by rank one matrices and an arbitrary rank matrix.

1) Then there exists a deterministic polynomial time algorithm which decides if $h$ is an element of $L$ of maximum rank. If $h$ is of maximum rank then a subspace $W$ of $U$ is constructed such that ${\rm rk\;}h=\dim U-(\dim W-\dim LW)$.

2) If $h$ is not of maximum rank then, given rank one transformations that together with $h$ span $L$, we can compute an element $h^{\prime}\in L$ with ${\rm rk\;}h^{\prime}>{\rm rk\;}h$ in deterministic polynomial time.

We may assume wlog that $\dim U=\dim V$, for otherwise we can pad transformations from $L$ with zeros to obtain a space $L^{\prime}\leq{\rm Lin}(U\oplus U^{\prime},V\oplus V^{\prime})$, where $\dim U\oplus U^{\prime}=\dim V\oplus V^{\prime}$ with some (possibly zero) spaces $U^{\prime},V^{\prime}$. By padding a transformation $b\in{\rm Lin}(U,V)$ we mean the map $b^{\prime}\in{\rm Lin}(U\oplus U^{\prime},V\oplus V^{\prime})$ which is the direct sum of $b$ and the zero map: $b^{\prime}(u,u^{\prime})=(bu,0)$.

Let $g:V\rightarrow U$ be an arbitrary nonsingular linear map such that $gh:U\rightarrow U$ is an idempotent. (The matrix of such a map $g$ can be obtained as the product of the matrices corresponding to the pivoting steps in Gaussian elimination for the matrix of $h$.) As $g$ is invertible, $h$ is of maximum rank within $L$ iff $gh$ is of maximum rank within $gL$. Also, rank one generators of $L$ are mapped to rank one generators of $gL$. If $gh$ is of maximum rank then by Lemma 4, ${\rm Env}(gL)\ker gh\leq ghU$. Conversely if ${\rm Env}(gL)\ker gh\leq ghU$ then, with $W_{0}:={\rm Env}(gL)\ker gh$ and $W_{1}:=\ker gh$, we have $gLW_{0},gLW_{1}\leq W_{0}\leq ghU$, and $W_{0}\cap W_{1}$=0 (if $v\in W_{0}\cap W_{1}$ then $v=ghu$ for some $u\in U$ and $ghv=0$, implying $0=ghghu=ghu=v$). Therefore with $W:=W_{0}+W_{1}\leq U$ we have $gLW\leq W_{0}$ and $\dim U-{\rm rk\;}gh=\ker gh=\dim W_{1}=\dim W-\dim W_{0}\leq\dim W-\dim gLW$. Now $g$ being invertible also implies that $\dim U-{\rm rk\;}h\leq\dim W-\dim LW$, which together with Fact 6 implies that $h$ has maximal rank. Thus if ${\rm Env}(gL)\ker gh\leq ghU$ then we can efficiently construct $W$ with the required property, it is a witness of the maximality of the rank of $gh$ (resp. $h$) in $gL$ (resp. $L$). Thus, $h$ and hence $gh$ is not of maximum rank if and only if ${\rm Env}(gL)\ker gh$ is not contained in $ghU$. This can be decided in an obvious way.

It is obvious that repeated applications of Theorem 7 completes the proof of Theorem 1.

Module Morphism Problems and Matrix Completion

In this section we present hardness results of certain problems concerning modules. The key constructions are modules that we call bipartite modules as they resemble bipartite graphs.

2 Universality of cyclic submodule optimization

3 Module morphisms

This shows that hard matrix completion problems do arise in module morphism spaces. However, curiously enough, deciding existence and construction of module isomorphisms, i.e., module homomorphisms which are bijective linear maps can be accomplished in polynomial time (see [CIK97] with some restriction for the base field and [BL08] over arbitrary fields). We show that this is not the case for testing existence of injective or surjective module morphisms.

Minimizing Number of Generators in Modules

A submodule of an ${\cal A}$-module is a linear subspace also closed under multiplication by elements of ${\cal A}$. The factor space of a submodule inherits the ${\cal A}$-module structure in a natural way and so do direct sums of linear spaces which are ${\cal A}$-modules. An ${\cal A}$-module $V$ is called simple if it has exactly two submodules: the whole $V$ and the zero submodule. The radical of a module is the intersection of its maximal (more precisely, maximal proper) submodules. A module $V$ is called semisimple if it is isomorphic to a direct sum of simple modules. By Section 2.7 of [Pie82], $V$ is semisimple if and only if its radical is the zero submodule. Furthermore, the factor module of $V$ by its radical is always semisimple. By Section 2.5 of [Pie82], the isomorphism classes of the constituents and their multiplicities in a decomposition of a semisimple module into a direct sum of simple modules are uniquely determined. Direct sums and homomorphic images of semisimple modules are semisimple.

where $V_{i}$ are pairwise non-isomorphic ${\cal A}$-modules. Let $V$ be an ${\cal A}$-module. As $V$ is a homomorphic image of at most $\dim V$ copies of the module ${\cal A}$, we have

where the multiplicities $s_{i}$ are non-negative integers.

2 A Greedy Optimization of the Submodule Dimension in Semisimple Modules

The annihilator ${\rm Ann}_{\cal A}(U)$ of $U\subseteq V$ is $\{a\in{\cal A}|au=0\mbox{~{}for every~{}}u\in U\}$. Note that the annihilator ${\rm Ann}_{\cal A}(v)$ of the single element $v\in V$ is just the kernel of the linear map $\mu_{v}:{\cal A}\rightarrow V$ given as $\mu_{v}(a)=av$. The following lemma states that if the rank of $\mu_{v}$ is not maximal then we are in the situation of Lemma 5.

Assume that $V$ is semisimple. Then, for an arbitrary $u\in V$, $\dim{\cal A}u=\max\{\dim{\cal A}u^{\prime}|u^{\prime}\in V\}$ iff ${\rm Ann}_{\cal A}(u)V\subseteq{\cal A}u$.

The lemma generalizes a result of Babai and Rónyai which was used in [BR90] for solving the cyclic submodule optimization in modules over simple algebras. The proof can be found in [CIK97]. For completeness, we discuss it here as well. The second part of the lemma is especially interesting for small base fields where Lemma 5 does not apply.

Let $V$ be a semisimple ${\cal S}$-module and let ${\cal A}={\rm Env}(I\cup\nu({\cal S}))$. Let ${\cal A}$ resp. $V$ be decomposed as in (3) resp. (4). Let $u\in V$. Assume that the dimension of the submodule ${\cal A}u$ is not maximal. Then, by Lemma 8, there exists an index $i$ such that the multiplicity of $V_{i}$ in ${\cal A}u$ is less than both $s_{i}$ and $m_{i}$. Let $W$ be the submodule of $V$ which is the direct sum of the constituents of $V$ not isomorphic to $V_{i}$. Then $V/W\cong V_{i}^{s_{i}}$ and $V/(W+{\cal A}u)$ is isomorphic $V_{i}^{h}$ with some $h>0$. Recall that for a subset $X$ of $V$ the annihilator of $X$ in ${\cal A}$, denoted by ${\rm Ann}_{\cal A}(X)$ is $\{a\in{\cal A}|ax=0\mbox{~{}for every~{}}x\in X\}$. Assume that ${\rm Ann}_{\cal A}(u)V\subseteq{\cal A}u$. Then every element of ${\rm Ann}_{\cal A}(u)$ act as zero on the factor module $V/{\cal A}u$ and hence also on the factor $V/(W+{\cal A}u)$. As the latter module is isomorphic to $V_{i}^{h}$ we obtain that ${\rm Ann}_{\cal A}(u)\subseteq{\rm Ann}_{\cal A}(V_{i})$. Recall that the map $\mu_{u}:{\cal A}\rightarrow V$ is given as $\mu_{u}(a)=au$. It is an ${\cal A}$-module homomorphism from the left module ${\cal A}$ to $V$. Its kernel is ${\rm Ann}_{\cal A}(u)$ and its image is ${\cal A}u$. Therefore ${\cal A}u\cong{\cal A}/{\rm Ann}_{\cal A}(u)$. Now ${\rm Ann}_{\cal A}(V_{i})$ is also an ${\cal A}$-submodule of ${\cal A}$. Let $L$ be a submodule of ${\cal A}$ isomorphic to $V_{i}$. We claim that $LV_{i}\neq 0$. Indeed, if $LV_{i}=0$ then, by the assumed isomorphism, $LL=0$ as well, which is impossible by Section 3.2 of [Pie82]. The claim implies that the multiplicity of $V_{i}$ in ${\rm Ann}_{\cal A}(V_{i})$ is zero and the same holds in ${\rm Ann}_{\cal A}(u)\subseteq{\rm Ann}_{\cal A}(V_{i})$. But then the multiplicity of $V_{i}$ in the factor module ${\cal A}/{\rm Ann}_{\cal A}(u)\cong{\cal A}u$ is $m_{i}$. This contradiction finishes the proof of: if ${\cal A}u$ is not of maximum dimension then in fact ${\rm Ann}_{\cal A}(u)V\not\subseteq{\cal A}u$.

To see the reverse implication, assume that ${\rm Ann}_{\cal A}(u)V\not\subseteq{\cal A}u$ and let $w\in V$ and $b\in{\rm Ann}_{\cal A}(u)$ such that $bw\not\in{\cal A}u$. By Section 2.4 of [Pie82], there exists a submodule $W^{\prime}$ of $V$ such that $W^{\prime}\cap{\cal A}u=0$ and $W^{\prime}+{\cal A}u=V$. Write $w=au+w^{\prime}$ where $a\in{\cal A}$ and $w^{\prime}\in W^{\prime}$. Put $u^{\prime}=u+w^{\prime}$. As ${\cal A}w^{\prime}\in W^{\prime}$, we have ${\cal A}u^{\prime}+W^{\prime}={\cal A}u+W^{\prime}$. On the other hand, from $bw\not\in{\cal A}u$ but $bau\in{\cal A}u$ we infer that $bw^{\prime}$ is a nonzero element of $W^{\prime}$ and by the equality $bu^{\prime}=bu+bw^{\prime}=bw^{\prime}$, it is also an element of ${\cal A}u^{\prime}$. Therefore $\dim{\cal A}u^{\prime}>\dim V-\dim W^{\prime}=\dim{\cal A}u$, as required.

For a polynomial time implementation of the construction above, notice that a basis for ${\rm Ann}_{\cal A}(u)$ can be found by solving a system of linear equations. Then $b$ and $w$ can be found by testing membership of products of pairs of basis elements for ${\rm Ann}_{\cal A}(u)$ and those for $V$. To compute a direct complement of ${\cal A}u$, we first compute a projection $\pi$ of $V$ onto ${\cal A}u$ such that $\pi a=a\pi$ for every element $a\in{\cal A}$ (equivalently, for every element of a system of generators for ${\cal A}$, say $\nu({\cal S})$). (Recall that a projection $\pi$ onto a subspace $V^{\prime}$ of $V$ is a map whose image is $V^{\prime}$ and it acts as the identity on $V^{\prime}$. If $W^{\prime}$ is submodule complementary to ${\cal A}u$ then the unique linear map which is the identity on ${\cal A}u$ and zero on $W^{\prime}$ is a projection onto ${\cal A}u$ which commutes with the action of ${\cal A}$ on $V$.) Once $\pi$ is constructed we take $\pi^{\prime}=I-\pi$. It is straightforward to see that the image $W^{\prime}=\pi^{\prime}V$ is in fact a direct complement of ${\cal A}u$. The element $w^{\prime}$ in the argument above is then just $\pi^{\prime}w$ and $u^{\prime}=u+\pi^{\prime}w$. This finishes the proof of Lemma 9. $\Box$

The next lemma can be used to give a generalization for submodules generated by larger systems (eg. noncyclic modules).

The two lemmas above together with Lemma 5 immediately give the following.

The above greedy property for the submodules of a semisimple module gives us the following technical lemma for general modules. It will be useful in the subsequent algorithm for optimizing the number of generators in any module without computing the radical explicitly.

Using the previous Lemma, now we describe an iterative algorithm to find a minimal set of generators of a given module over a sufficiently large ground field.

If $W^{\prime}=W$ then output $U$ and exit. Inner loop:

If $W\not\leq U+W^{\prime}$ then continue inner loop with $W^{\prime}=(U+W^{\prime})\cap W$. Else continue outer loop with $W=W^{\prime}$.

Over small base fields we use the algorithm of [FR85] or [CIW97] to compute the radical of ${\cal A}$ and the radical $V_{0}$ of $V$ therefrom and compute a minimal generating set $\Gamma_{0}$ of the factor module $V/V_{0}$ using Proposition 12 directly. For each $u_{0}\in\Gamma_{0}$ we pick a representative $u\in u_{0}+V_{0}$ and obtain a subset $\Gamma\subseteq V$ such that $|\Gamma|=|\Gamma_{0}|$ and $\Gamma\cup V_{0}$ generates $V$. By a standard property of the radical, we show that $\Gamma$ itself generates $V$. Indeed, let $U$ be the submodule generated by $\Gamma$. If $U\neq V$ then there is a maximal (proper) submodule $U^{\prime}\supseteq U\supseteq\Gamma$. But $U^{\prime}\geq V_{0}$ by the definition of $V_{0}$, therefore $U^{\prime}\supseteq\Gamma\cup V_{0}$, implying $U^{\prime}\supseteq V$, which is a contradiction to $U^{\prime}$ being proper. This ends the proof of Theorem 3.

Concluding remarks

We have shown that the maximum rank matrix in a linear space generated by rank one matrices and a further matrix of arbitrary rank can be found in deterministic polynomial time if the rank one generators are given. It would be interesting to know if there is an efficient deterministic method in the case where the rank one generators are not known. In this direction we have a deterministic polynomial time algorithm, which, given a matrix of maximum rank constructs a certificate that the rank is in fact maximal (see Theorem 7) without knowing the rank one generators. This implies that over sufficiently large base fields, the maximum rank matrix can be constructed in Las Vegas polynomial time. The best result of this flavor is the deterministic polynomial time algorithm of Gurvits [Gur03, Gur04] which decides whether there exists a nonsingular matrix in the space generated by rational matrices under the assumption that the span over the complex numbers can be generated by unknown rank one matrices (with not necessarily rational entries). Unfortunately, this algorithm decides the mere existence of a nonsingular matrix without explicitly constructing one.

Acknowledgements

We would like to thank the anonymous referees for several suggestions. We are grateful to the Hausdorff Research Institute for Mathematics, Bonn for its hospitality and the kind support.

References