SIAM J. MATRIX ANAL. APPL. ©c 2002 Society for Industrial and Applied Mathematics
Vol. 24, No. 2, pp. 570–580
ON MATRICES WITH SIGNED NULL-SPACES∗
SI-JU KIM† , BRYAN L. SHADER‡ , AND SUK-GEUN HWANG§
Abstract. We denote by Q(A) the set of all matrices with the same sign pattern as A. A
matrix A has signed null-space provided there exists a set S of sign patterns such that the set of sign
patterns of vectors in the null-space of Ã is S for each Ã ∈ Q(A). Some properties of matrices with
signed null-spaces are investigated.
Key words. totally L-matrices, signed compounds, signed null-spaces
AMS subject classification. 05C50
PII. S0895479801396221
1. Introduction. The sign of ⎧a real number a is defined by⎨ −1 if a < 0,
sign(a) = ⎩ 0 if a = 0, and
1 if a > 0.
A sign pattern is a (0, 1,−1)-matrix. The sign pattern of a matrix A is the matrix
obtained from A by replacing each entry with its sign. We denote by Q(A) the set of
all matrices with the same sign pattern as A.
Let A be an m by n matrix and b an m by 1 vector. The linear system Ax = b
has signed solutions provided there exists a collection S of n by 1 sign patterns such
that the set of sign patterns of the solutions to Ãx = b̃ is S for each Ã ∈ Q(A) and
b̃ ∈ Q(b). This notion generalizes that of a sign-solvable linear system (see [1] and
references therein). The linear system, Ax = b, is sign-solvable provided each linear
system Ãx = b̃ (Ã ∈ Q(A), b̃ ∈ Q(b)) has a solution and all solutions have the same
sign pattern. Thus Ax = b is sign-solvable if and only if Ax = b has signed solutions
and the set S has cardinality 1.
The matrix A has signed null-space provided Ax = 0 has signed solutions. Thus
A has signed null-space if and only if there exists a set S of sign patterns such that
the set of sign patterns of vectors in the null-space of Ã is S for each Ã ∈ Q(A).
An L-matrix is a matrix A, with the property that each matrix in Q(A) has linearly
independent rows. A square L-matrix is a sign-nonsingular (SNS)-matrix. A totally
L-matrix is an m by n matrix such that each m by m submatrix is an SNS-matrix.
It is known that totally L-matrices have signed null-spaces [3]. We also have the fact
as a corollary of some results in this paper. Thus matrices with signed null-spaces
generalize totally L-matrices.
A vector is mixed if it has a positive entry and a negative entry. A matrix is row-
mixed if each of its rows is mixed. A signing is a nonzero diagonal (0, 1,−1)-matrix.
∗Received by the editors October 8, 2001; accepted for publication (in revised form) by R. Wabben
May 23, 2002; published electronically December 19, 2002.
http://www.siam.org/journals/simax/24-2/39622.html
†Department of Mathematics Education, Andong National University, Andong, 760-749 Republic
of Korea, (sjkim@andong.ac.kr). The research of this author was supported by Andong National
University.
‡Department of Mathematics, University of Wyoming, Laramie, Wyoming 82071 (bshader@
uwyo.edu).
§Department of Mathematics Education, Kyungpook University, Taegu, 702-701, Republic of
Korea (sghwang@knu.ac.kr). The research of this author was supported by Com2MaC.
570
MATRICES WITH SIGNED NULL-SPACES 571
A signing is strict if each of its diagonal entries is nonzero. A matrix B is strictly
row-mixable provided there exists a strict signing D such that BD is row-mixed.
In this paper, some properties of matrices with signed null-spaces are investigated,
and we show that there exists an m by n matrix A with signed null-space such that
A contains a totally L-matrix with m rows as its submatrix and the columns of A are
distinct up to multiplication by −1 for any n ∈ {m,m+ 1, . . . , 2m}.
We use the following standard notation throughout the paper. If k is a positive
integer, then 〈k〉 denotes the set {1, 2, . . . , k}. Let A be an m by n matrix. If α
is a subset of {1, 2, . . . ,m} and β is a subset of {1, 2, . . . , n}, then A[α|β] denotes
the submatrix of A determined by the rows whose indices are in α and the columns
whose indices are in β. We sometimes use A[∗|β] instead of A[〈m〉|β]. The submatrix
complementary to A[α|β] is denoted by A(α|β). In particular, A(−|β) denotes the
submatrix obtained from A by deleting columns whose indices are in β. We write
diag(d1, d2, . . . , dn) for the n by n diagonal matrix whose (i, i)-entry is di. Let Jm,n
denote the m by n matrix, all of whose entries are 1, and let ei denote the column
vector, all of whose entries are 0 except for the ith entry, which is 1.
2. Matrices with signed null-space. We say that an m by n matrix A =
[aij ] contains a mixed cycle provided there exist distinct i1, i2, . . . , ik and distinct
j1, j2, . . . , jk such that
ai ,j ai ,j < 0 for t = 1, . . . , k − 1 and at t t t+1 ik,j ai ,j < 0.k k 1
An m by n (0, 1,−1)-matrix has signed mth compound provided each of its m by
m submatrices having term rank m is an SNS-matrix.
We make use of the following results of matrices with signed null-spaces.
Theorem 2.1 (see [3]). Let A be a strictly row-mixable m by n matrix. Then
the following three conditions are equivalent.
(a) A has signed null-space.
(b) A has term rank m, and its mth compound is signed.
(c) AD has no mixed cycle for each strict signing such that AD is row-mixed.
Theorem 2.2 (see [2], [3]). If a strictly row-mixable matrix A has signed null-
space, then there exist matrices B and C (possibly with no rows) and nonzero vectors
b and c such that B and C are [strict]ly row-mix[able m] atrices with signed null-spaces,
B c
and
b C
have signed null-spaces, and, up to perm⎡utation o⎤f rows and columns,
B O
A = ⎣ b c ⎦ .
O C
The converse also holds.
Let A be an m by n (0, 1,−1)-matrix. The matrix B is conformally contractible
to A provided there exists an index k such that the rows and columns of B can be
permuted so that B has the[ form ]
A[〈m〉|〈n〉 \ {k}] x y
0 · · · 0 1 − ,1
where x = [x1, . . . , xm]
T and y = [y1, . . . , y
T
m] are (0, 1,−1)-vectors such that xiyi ≥
0 for i = 1, 2, . . . ,m, and the sign pattern of x+ y is the kth column of A.
572 SI-JU KIM, BRYAN L. SHADER, AND SUK-GEUN HWANG
Let B be conformally contractible to A. It is known that A has signed null-space
if and only if B has signed null-space [3]. All matrices we consider from now on are
assumed to be (0, 1,−1)-matrices.
Theorem 2.3 (see [4]). Let an m by n matrix A have a k by k + 1 submatrix
B whose complementary submatrix in A has term rank m − k. If there is a matrix
B∗ obtained from B by replacing some nonzero entries with 0’s if necessary such that
J2,3 is the zero pattern of a matrix obtained from B
∗ by a sequence of conformal
contractions, then A does not have signed null-space.
Let M be an m by n strictly row⎡-mixable matr⎤ix of the form
⎢ 0⎢⎢ .. ⎥(2.1) M = ⎣ ∗ . ⎥⎥ .0 ⎦
1 1
Proposition 2.4. M ha⎡s signed null-space if and only⎤if
⎢ 0
⎣⎢⎢ M .
.
A = . ⎥⎥⎥
0 ⎦
0 · · · 0 1 −1 1
has signed null-space.
Proof. Let M have signed null-space, and let C be any m+1 by m+1 submatrix
of A. If C contains the last column of A, then C(m+1|m+1) is an m by m submatrix
of M . Hence C(m + 1|m + 1) is an SNS-matrix, or C(m + 1|m + 1) has identically
zero determinant by Theorem 2.1. Thus C is an SNS-matrix, or C has identically
zero determinant. Hence we may assume that C does not contain the last column of
A. If C contains neither the n− 1th column nor the nth column, then clearly C has
identically zero determinant. If C contains only one of the (n−1)th column or the nth
column, then C(m+ 1|m+ 1) is an m by m submatrix of M . Hence C(m+ 1|m+ 1)
is an SNS-matrix, or C(m + 1|m + 1) has identically zero determinant. Therefore,
C is an SNS-matrix, or C has identically zero determinant. Let C contain both the
(n− 1)th column and the nth column of A. Then C(m+1|m+1) is an SNS-matrix,
or C(m+1|m+1) has identically zero determinant. If C(m+1|m+1) has identically
zero determinant, then there exists an s by t zero submatrix of C(m+ 1|m+ 1) such
that s+ t = m+ 1. From this, it is easy to show that C has a p by q zero submatrix
such that p+ q = m+2; i.e., C has identically zero determinant. Let C(m+1|m+1)
be an SNS-matrix. Since C is conformally contractible to C(m+ 1|m+ 1), C is also
an SNS-matrix. Thus the (m + 1)th compound of A is signed. Since M has signed
null-space, the term rank of M is m, and hence the term rank of A is m+1. Thus A
has signed null-space by Theorem 2.1. The converse is trivial.
We say that A is a single extension of M in Proposition 2.4. Proposition 2.4
means that a strictly row-mixable matrix has signed null-space if and only if its single
extension has signed null-space.
Let ⎡ ⎤
⎢ 0⎢⎢⎣ ∗ .
.
. ⎦⎥
⎥
G = ⎥
0
0 · · · 0 1 1 1
MATRICES WITH SIGNED NULL-SPACES 573
be an m by n matrix, and⎡let ⎤
⎣ G OH = 0 · · · 0 0 1 −1 1 0 ⎦ .
0 · · · 0 1 0 −1 0 1
Proposition 2.5. The m by n strictly row-mixable matrix G has signed null-
space if and only if H has signed null-space.
Proof. Let G have signed null-space, and let C = [cij ] be an m + 2 by m + 2
submatrix of H. That is, C = H[∗|β] for some β ⊂ 〈n + 2〉. If n + 2 ∈ β, then
H[〈m+1〉|β \ {n+2}] is an SNS-matrix, or it has identically zero determinant since
H(m + 2|n + 2) is a single extension of G. Hence C is an SNS-matrix, or C has
identically zero determinant. Similarly, we can show that C is an SNS-matrix or C
has identically zero determinant if n+ 1 ∈ β. Hence we may assume that β contains
neither n+1 nor n+2. Then it is easy to show that C has identically zero determinant
if β contains at most two among n−2, n−1, and n. Let {n−2, n−1, n} ⊂ β. Then
H[〈m〉|β \ {n − 1, n}] is an SNS-matrix or it has identically zero determinant since
G has signed null-space. If H[〈m〉|β \ {n − 1, n}] has identically zero determinant,
then clearly C has identically zero determinant. Let H[〈m〉|β \ {n − 1, n}] be an
SNS-matrix. Then H[〈m− 1〉|β \ {n− 2, n− 1, n}] is an SNS-matrix since cmm = 1.
Since C is in the⎡form of ⎤
⎢ H[〈m− 1〉|β \ {n− 2, n− 1, n}] ∗⎣⎢ 1 1 1 ⎥⎥O 0 1 −1 ⎦
1 0 −1
and C[m,m+1,m+2|m,m+1,m+2] is also an SNS-matrix, C is an SNS-matrix.
The converse is trivial.
We say that H is a double extension of G in Proposition 2.5. That G should have
a row with exactly three ones is ne[cessary in Proposit]ion 2.5. For example, let
1 1 1 −1
A =
1 −1 0 0
and ⎡ ⎤
⎢ 1 1 1 −1 0 0⎢⎣ 1 −1 0 0 0 0 ⎥B = ⎥0 1 −1 0 1 0 ⎦ .
1 0 −1 0 0 1
Then B is a double extension of A that has signed null-space. But B[1, 2, 3, 4|1, 2, 3, 4]
is a mixed submatrix of A, and hence B does not have signed null-space.
Corollary 2.6. Every totally L-matrix has signed null-space.
Proof. From Propositions 2.4 and 2.5, we have the result.
Proposition 2.7. Let A be a strictly row-mixable m by n matrix with no du-
plicate columns up to multiplication by −1. If A has signed null-space and is not
conformally contractible to a matrix, then it has at least two rows with exactly three
nonzero entries.
Proof. Without loss of generality, we may assume that each row of A has at least
three nonzero entries and A has no zero column. Notice that m ≥ 2 comes from the
574 SI-JU KIM, BRYAN L. SHADER, AND SUK-GEUN HWANG
condition. We prove the result by induction on m. Trivially, we have the result for
m = 2. Let m ≥ 3. By Theorem 2.2, A⎡can be re⎤arranged as
A = ⎣ B Ob c ⎦ ,
O C
where matrices B and C (possibly with no rows) are strictly row-mixable matrices
which have signed null-spaces, a[nd ve]ctors b an[d c a]re nonzero.
B c
and
b [ ] C [ ]
also have signed null-spaces. Let A[α|β] = Bb and A[γ|δ] =
c
C such that |α| =
k, |β| = s, |γ| = l, and |δ| = t. Then k + l − 1 = m and s+ t = n.
Let k > 1 and l > 1. If A[α|β] has one of the unit vectors ±ek as a column, then
we can assume that A[α|β] is of the [form′ ]
B O
′ .
b 1
′ ′
Let B have no duplicate columns up to multiplication by −1. By induction, B
and hence A have at least two rows with exactly three nonzero entries. Thus we are
′
done. Therefore, we assume that B has duplicate columns up to multiplication by
− ′ ′1. Then b = 0. If b has at least two nonzero entries, then A[α|β] is a strictly row-
mixable matrix with no duplicate columns up to multiplication by −1. Since A[α|β]
is not conformally contractible to a matrix, B has at least one row with exactly three
′ ′
nonzero entries. Let b have exactly one nonzero entry. Let the columns 1, 2 of B be
a pair of duplicate columns up to multiplication by −1, and let p be the number of
′ ′
nonzero entries in the column 1 of B . Let D be a strict signing such that M = B D
′
is row-mixed. Since B has signed null-space, M has no mixed cycle, and hence the
′
columns 1 and 2 of M must be identical or p = 1. If p ≥ 2, then the matrix M
′
obtained from M by multiplying the column 2 by −1 has a mixed cycle. Thus M is a
row-mixed matrix with signed null space, which is impossible by Theorem 2.1. Hence
′
p = 1. Therefore, every duplicate column of B is of the form ei or −ei for some i.′
Hence B has only one pair of duplicate columns, which are ei or −ei for some i(< k).′
The matrix obtained from B by deleting one of the duplicate columns, which are ei or
−ei, satisfies the conditions of the hypothesis if its ith row has at least three nonzero
entries. This implies that B has at least one row with exactly three nonzero entries.
′ ′
Let C = A[γ|{s} ∪ δ]. Similarly, C has a row i with exactly three nonzero entries
for some i(= 1). Hence C has at least one row with exactly three nonzero entries.
Therefore, A has at least two rows with exactly three nonzero entries. Similarly, in
the case in which A[γ|δ] has one of the unit vectors ±e1 as a column, we have the
result. Assume that A[α|β] and A[γ|δ] do not have the unit vectors ±ek and ±e1,
respectively, as columns. Since b is nonzero, the k by s+ 1 matrix B∗ obtained from
A[α|β] by adding ek as a column is a strictly row-mixable matrix with no duplicate
columns up to multiplication by −1. Since B has signed null-space, B∗ also has signed
null-space. Applying the similar method above to B∗, we can derive that B has at
least one row with exactly three nonzero entries. Similarly, C also has at least one
row with exactly three nonzero entries. Hence we have the result when k > 1 and
l > 1.
MATRICES WITH SIGNED NULL-SPACES 575
Let k = 1. Then s = 1 since the columns of A are distinct up to multiplication
by −1. Hence we may assume that A[= [aij ] i]s of the form
1 c
.
O C
If C has no duplicate columns up to multiplication by −1, then we have the result for
C by induction, and hence we have the result for A. Let C have duplicate columns
up to multiplication by −1. Then the duplicate columns of C are of the form ei or
−ei for some i, as we have shown before. This implies that the number of identical
columns of C up to multiplication by −1 is at most 3. Therefore, we may assume
that the ze⎡ro pattern of A is of the form ⎤
⎢⎢⎢
1 u · · · u v · · · v w · · · w 0 or 1
x ⎥
⎢ ⎥⎢ . ⎥⎢⎢⎢
. . ⎥⎥
x ⎥
⎢⎢⎢
⎥
v ⎥⎥
⎢⎢⎢
. . . S ⎥⎥⎥
⎢ v ⎥⎥⎢⎢ v ⎥
,
⎢ ⎥⎢⎢⎢
. ⎥. .
⎢ v ⎥
⎥⎥
⎢ ⎥⎣ ⎥⎥T ⎦
where u = (1, 1, 0), v = (1, 1), w = (1, 0), and x = (1, 1, 1), and the unsp[ec]ified entries
are zero. Let be the set of indices of columns in A corresponding to ST . Then we
may also assume that A[γ \ {1}|] has no duplicate columns up to multiplication by
−1, and t[he]columns are also different from the ones of A(1|) up to multiplication
by −1. If ST is vacuous, we are done since l ≥ 3 and every row but the first row of A
has at least three nonzero entries. Let only T be vacuous. Notice that each column
of S has at least two nonzero entries. Hence each row of S has at most one nonzero
entry. For, suppose that a row of S has two nonzero entries. Since the columns of
A[γ \ {1}|] are distinct up to multiplication by −1, we may assume that there exists
a submatrix of A whose zero pattern is
⎡ ⎤ ⎡ ⎤
∗ ∗ ⎢ 1 1 1 ∗ ∗⎣ 1 1 ⎦ ⎢⎣ 1 0 0 1 11 0 1 1 or 0 1 0 1 ∗ ⎦⎥⎥ ,
0 1 1 1
0 0 1 ∗ 1
where * is 0 or 1. By Theorem 2.3, A does not have signed null-space. This is a
contradiction. Next, suppose that a row r of A[γ \ {1}|〈n〉] has four nonzero entries.
Since each row of S has at most one nonzero entry and each column of S has at least
two nonzero entries, we have a su⎡bmatrx of A wh⎤ose zero pattern is
⎣ 1 1 1 ∗1 1 0 1 ⎦ ,
0 0 1 1
576 SI-JU KIM, BRYAN L. SHADER, AND SUK-GEUN HWANG
which is also impossible by Theorem 2.3. Hence each row of A[γ \{1}|〈n〉] has exactly
three nonzero entries. Thus we have the result when T is vacuous. Let T be nonva-
cuous. Notice that the submatrix of A corresponding to T is a strictly row-mixable
′
matrix with signed null-space. Let T be the matrix obtained from T by deleting zero
′ ′
columns. Then we may assume that T is of the form [O T ]. If the submatrix A
′
of A corresponding to T has no duplicate columns up to multiplication by −1, then
′
A has at least two rows with exactly three nonzero entries by induction. Hence we
′
have the result. Suppose that A has duplicate columns up to multiplication by −1.
′
It is easy to show that such columns of A have exactly one nonzero entry as we have
′
shown above. We want to show that the number of identical columns of A is at most
′
three. Suppose that there are four identical columns in A up to multiplication by −1.
We may assume that the zero pattern of the submatrix consisting of such duplicate
′
columns of A is of the form [ ]
1 1 1 1
.
O
Since A[γ\{1}|] has no duplicate columns up to multiplication by −1, we may assume
that A[γ \ {1}|] has a submatrix whose zer⎡o pattern is⎡ ⎤ ⎤
⎣ 1 ∗ ∗ ⎢
1 ∗ ∗
∗ ⎦ ∗ 1 ∗ ⎥1 1 or⎢⎣ ⎥∗ ∗ ,1 ⎦
1 1 1
1 1 1
where * is 0 or 1. Hence we can have a su⎡bmatrix N of A whos⎤e zero pattern is⎡ ⎤
∗ ∗ ∗ ⎢ 1 1 1 ∗ ∗ ∗⎢ 1 1⎢ ∗ ∗ ⎥⎥ ⎢ 1 0 0 1 ∗ ∗ ⎥⎣ 1 0 1 ⎥∗ ⎦ or⎢ 0 1 0 ∗ 1 ∗ ⎥ ,0 1 1 1 ⎢⎣ ⎥0 0 1 ∗ ∗ 1 ⎦
0 0 1 1 1
0 0 0 1 1 1
where * is 0 or 1. By Theorem 2.3, A does not have signed null-space. This is a
′
contradiction. Thus we can assume [that T is o]f the form′ ′
T1 T2′ ,
O T3
′
where T1 is a block diagonal matrix whose[ di]agonal blocks are either [1 1] or [1 1 1],′T
and the submatrix of A corresponding to 2′ has no duplicate columns up to multi-
T3
plication by −1. Continuing this ⎡process, we can⎤assume that T is of the form
⎢ T⎣ 1
∗
.
O . . ⎦⎥ ,
Tq
′ ′
where Ti = [O Ti ] for i = 1, 2, . . . , q and Ti are block diagonal matrices whose diagonal
blocks are either [1 1] or [1 1 1] for i = 1, 2, . . . , q − 1.
Let λi be the set of indices of rows in A corresponding to Ti. Let i and δi
be the set of indices of nonzero columns in A and zero columns in A corresponding
MATRICES WITH SIGNED NULL-SPACES 577
to Ti, respectively. It is easy to show that each row of A[λi|i ∪ δi+1] has at most
three nonzero entries for i = 1, 2, . . . , q − 1 by a method similar to that used in the
′ ′
case in which only T is vacuous. If the submatrix Aq of A corresponding to Tq has
′
no duplicate columns up to multiplication by −1, then Aq satisfies the hypothesis.
′
Hence we have the result. If Aq has duplicate columns up to multiplication by −1,
′ ′′ ′′′ ′′
then we may assume that Tq = [Tq Tq ], where Tq is a block diagonal matrix whose
diagonal blocks are [1 1] or [1 1 1]. As we have shown above in the case in which T
′ ′
is vacuous, each row of Tq has exactly three nonzero entries. If Tq has at least two
rows, then we are done.
′
Thus we may assume that Tq = [1 1 1]. Then A[〈m − 1〉|n − 2, n − 1, n] cannot
have a row whose zero pattern is equal to (1, 1, 1) because, if so, then A has J2,3 as a
submatrix, and this is impossible by Theorem 2.3. If A[m−1|n−2, n−1, n] = O, then
we are done. Hence we may assume that the zero pattern of A[m− 1|n− 2, n− 1, n]
is either [1 1 0] or [1 0 0].
Let the zero pattern of A[m − 1|n − 2, n − 1, n] be [1 1 0]. If the rth row of
A[〈m − 2〉|n − 2, n − 1, n] has the zero pattern (1, 1, 0) for some r, then there exist
distinct i1, i2, . . . , ik and distinct j1, j2, . . . , jk such that ai1,j1 , ai2,j1 , . . . , aik,j arek
nonzero, where i1 = 1, ik = r, and jk = n− 2. There also exist distinct p1, p2, . . . , pt
and distinct q1, q2, . . . , qt such that ap ,q , ap ,q , . . . , ap ,q are nonzero, where p =1 1 2 1 t t 1
1, pt = m − 1, and qt = n − 2. Choosing some entries from these entries, we have a
matrix which is conformally contractible to a matrix whose zero pattern is J2,3. This
is impossible by Theorem 2.3. We can apply a method similar to that used above to
show that A[〈m− 2〉|n] = O. Hence each row of A[〈m− 2〉|n− 2, n− 1, n] has a zero
′
pattern of the forms (0, 0, 0), (1, 0, 0), or (0, 1, 0). Let Tq−1 have at least two rows. It
is easy to show that, if each row of A[λq−1|q−1 ∪ δq ∪ q] has at least four nonzero
entries, we have a submatrix of A which is conformally contractible to a matrix whose
zero pattern is J2,3 by the method just used above. By Theorem 2.3, it is impossible.
Hence some row of A[λq−1|q−1 ∪ δq ∪ q] has exactly three nonzero entries. Thus we
′ ′
have the result when Tq−1 has at least two rows. Therefore, we may assume that Tq−1
′
is either [1 1] or [1 1 1]. Notice that Tq = Tq = [1 1 1].
′
Let Tq−1 = [1 1 1]. If A[〈m − 2〉|n − 2, n − 1, n] = O, then we can show that
there exists a submatrix of A which is conformally contractible to a matrix whose
zero pattern is J2,3. This is impossible. Hence we may assume that A[〈m − 2〉|n −
2, n − 1, n] = O. Then A[〈m − 1〉|〈n − 3〉] has at least two rows with exactly three
′
nonzero entries by induction. Hence we are done. Let Tq−1 = [1 1]. Notice that
A[〈m− 2〉|n− 4, n− 3] has no submatrix whose zero pattern is J2,2 by Theorem 2.1.
That is, all rows of A[〈m−2〉|n−4, n−3] except for one row have at least one zero entry.
Since the conformal contraction of A[〈m−1〉|〈m−3〉] on the last row has signed null-
space, A[〈m−1〉|〈n−3〉] has at least one row with exactly three nonzero entries. Thus
we have the result if A[〈m−2〉|n−2, n−1, n] = O. Let A[〈m−2〉|n−2, n−1, n] = O.
Since we are done if the (m − 2)nd row of A has exactly three nonzero entries, we
may assume that the (m− 2)nd row of A has at least four nonzero entries. Deleting
the cases in which a contradiction occurs, we may assume that the zero pattern of
A[m− 2,m− 1,m|n− 6, n− 5, n− 4, n− 3, n− 2, n− 1, n] is
⎡ ⎤
⎣ 1 1 1 0 1 0 00 0 1 1 1 1 0 ⎦ .
0 0 0 0 1 1 1
578 SI-JU KIM, BRYAN L. SHADER, AND SUK-GEUN HWANG
It is easy to show that A[〈m−2〉|n−1, n] = O by using a method similar to that used
above. If the columns of A[m−2,m−1|n−4, n−2] are identical up to multiplication by
−1, then it is easy to find a strict signing D such that AD is a row-mixed matrix and
A[m−2,m−1|n−4, n−2]D contains a mixed cycle. This is impossible by Theorem 2.1.
Hence the columns of A[〈m − 1〉|〈n〉] are not identical up to multiplication by −1.
Therefore, A[〈m− 1〉|〈n− 2〉] satisfies the hypothesis. Thus we have the result when
the zero pattern of A[m− 1|n− 2, n− 1, n] is [1 1 0].
In the case in which the zero pattern of A[m − 1|n − 2, n − 1, n] is [1 0 0], the
last row of A[〈m − 1〉|〈n − 3〉] must have two or three nonzero entries. If it has two
nonzero entries, then we are done. Let it have three nonzero entries. Then we have
a submatrix of A which is conformally contractible to a matrix whose zero pattern is
J2,3 if A[〈m− 2〉|n− 2, n− 1, n] = O by a method similar to that used above. Hence
we have A[〈m − 2〉|n − 2, n − 1, n] = O. Therefore, A[〈m − 1〉|〈n − 3〉] has at least
two rows with exactly three nonzero entries by induction. Thus we have the result
for k = 1. Similarly, we have the same result for l = 1.
3. Matrices containing totally L-matrices. Let A be a matrix with signed
null-space. A is a maximal matrix with signed null-space if any matrix obtained from
A by replacing a zero entry with a nonzero entry does not have signed null-space.
Lemma 3.1. An m by m + 2 totally L-matrix is a maximal matrix with signed
null-space.
Proof. Let A be an m by m + 2 totally L-matrix. Let A∗ be an m by m + 2
matrix obtained from A by replacing a zero entry with 1 or −1. Notice that every
m by m submatrix of A∗ has term rank m. Since A∗ has a row with four nonzero
entries, A∗ is not a totally L-matrix. Therefore, there exists an m by m submatrix of
A∗ that is not an SNS-matrix. Hence A∗ does not have signed null-space by Theorem
2.1.
Lemma 3.2. Let A be an m by m + 2 totally L-matrix, and let x be an m by 1
column vector which has at least two nonzero entries. Then B = [A x] does not have
signed null-space.
Proof. We will prove the result by induction on m. The statement is clear for
m = 2. We may assume that [ ]
′ O
B = [bij ] = M x ,I2
where I2 is the identity matrix of order 2. If bm−1,m+3 = 0 or bm,m+3 = 0, say,
bm,m+3 = 0, then B(m|m + 2) does not have signed null-space by induction. Hence
we have the result by Theorem 2.3. Therefore, we may assume that the last two
positions of x have nonzero entries. Since a totally L-matrix is a maximal matrix
with signed null-space, B(−|m + 2) does not have signed null-space. Hence B does
not have signed null-space.
We say that an m by m + 2 totally L-matrix contains k double-extensions (or
m− 2k − 2 single-extensions) if A[ is obtained from]
1 1 1 0
1 −1 0 1
by a sequence of m− 2k− 2 single-extensions and k double-extensions up to row and
column permutations and multiplication of rows and columns by −1.
Proposition 3.3. Let A be an m by n matrix with signed null-space whose
MATRICES WITH SIGNED NULL-SPACES 579
columns are nonzero and distinct up to multiplication by −1. If A contains an m by
m+ 2 totally L-matrix with k double-extensions, then n ≤ 2m− 2k.
Proof. We will prove the result by induction on k. Let Tk be an m by m + 2
totally L-matrix with k double-extensions contained in A. Notice that each column
of A which does not correspond to Tk has exactly one zero entry by Lemma 3.2. If
k = 0, then it is known [1] that Tk has a signed rth compound for each r = 1, 2, . . . ,m.
Hence we can have the identity matrix Im as a submatrix of A. Since T0 has exactly
two columns with exactly one nonzero entry, n ≤ m+ 2 + (m− 2) = 2m = 2m− 2k.
Let k = 0. By Proposition⎡ 2.4 and Lemma 3.2, we may a⎤ssume that A is of the form
⎢ A1 A2 O⎢⎢ 1 −1 0 0 0 ⎥⎢ A ⎥⎣ 3 1 1 −1 0 00 1 1 1 0 ⎦⎥⎥ .
O
1 0 1 0 1
Then A(m − 1,m|n − 1, n) has signed null-space, and it contains an m − 2 by m
totally L-matrix with k − 1 double-extensions. The columns of A(m− 1,m|n− 1, n)
are distinct up to multiplication by −1 because, if not, then A3 has a column of the
forms (0, 1)T or (0,−1)T , say, (0, 1)T⎡ . Then A has a ⎤submatrix
⎢ 0 1 −1 01 1 1 −1 ⎥
(3.1) B = ⎣⎢ ⎥0 0 1 1 ⎦ ,
0 1 0 1
which is not an SNS-matrix. Since A contains an m by m + 2 totally L-matrix,
the complementary submatrix to B in A has term rank m − 4. Hence A does not
have signed null-space by Theorem 2.1. This is a contradiction. Therefore, n − 2 ≤
2(m− 2)− 2(k − 1) = 2m− 2k − 2 by induction. Thus we have n ≤ 2m− 2k.
Let l be the number of single-extensions contained in A. Then we have l = m−
2k−2. Hence we can restate the result of Proposition 3.3 in terms of l: n ≤ m+ l+2.
Corollary 3.4. Let T be an m by m + 2 totally L-matrix which contains no
single-extensions. Then there is no m by n matrix A with signed null-space such
that A contains T properly, and the columns of A are nonzero and distinct up to
multiplication by −1.
Proof. Let A be an m by n matrix with signed null-space, and let A contain T .
Since T contains no single-extensions, l = 0. Hence n ≤ m + l + 2 = m + 2. Hence
A = T .
Let M be an m by n matrix of the form in (2.1) with signed null-space, and let
A be the m+ 1 by n+ 2 m⎡atrix such that ⎤
⎢ 0 0⎢⎢ .. . ⎥. .. ⎥⎥M
A = ⎢⎢⎣ 0 0 ⎥⎥ .1 0 ⎦
0 · · · 0 1 0 −1 1
Since A(−|n+2) is conformally contractible to M , A(−|n+2) has signed null-space.
Since M has signed null-space, A has signed null-space by Theorem 2.1. Let Tk be
an m by m + 2 totally L-matrix with k double-extensions. Let {i1, i2, . . . , il} with
580 SI-JU KIM, BRYAN L. SHADER, AND SUK-GEUN HWANG
i1 < i2 < · · · < il be the set of indices of rows used when single-extensions are
constructed in Tk. Notice that Tk does not contain any ei , j = 1, 2, . . . , l. Thej
remark above and Proposition 2.5 imply that
(3.2) T = [Tk ei e . . . e ]1 i2 il
is an m by 2m − 2k matrix whose columns are distinct up to multiplication by −1,
and it has signed null-space.
Let j be the index of a row of Tk used when a double-extension is done, and
suppose that Tk does not have ej as a column. [Tk ej ] has a submatrix of the form in
(3.1), and hence it does not have signed null-space, as we have shown in the proof of
Proposition 3.3.
Let Tk be the set of all matrices of the form in (3.2). Notice that columns of
A ∈ Tk are nonzero and distinct up to multiplication by −1. We can express the m
by n matrices A with n = 2m− 2k in Proposition 3.3 in terms of elements of Tk.
Proposition 3.5. In Proposition 3.3, n = 2m − 2k if and only if there exists
a permutation matrix Q such that A is equal to TQ up to multiplication of rows and
columns by −1 for some T ∈ Tk.
Proof. Let A be anm by nmatrix such that A = TQ for some permutation matrix
Q and T ∈ Tk. Then m = 2k+ l+2, and hence n = m+2+ l = m+2+(m−2−2k) =
2m − 2k. Conversely, let A be an m by 2m − 2k matrix satisfying the conditions in
Proposition 3.3. Let Tk be an m by m+ 2 totally L-matrix with k double-extensions
contained in A. Then there exists a permutation matrix Q and strict signings D, E
such that DAQE is a submatrix of matrix T of the form in (3.2) by Lemma 3.2 and
the remark above. Since T is an m by 2m− 2k matrix, A = DTQ−1E. Since T ∈ Tk,
we have the result.
Corollary 3.6. Let m be a positive integer with m ≥ 2, and let n be any integer
in {m,m+ 1, . . . , 2m}. Then there exists an m by n matrix A with signed null-space
such that A contains a totally L-matrix with m rows as its submatrix and the columns
of A are nonzero and distinct up to multiplication by −1.
Proof. Let n be any integer in {m,m + 1, . . . , 2m}. If n ≤ m + 2, then we can
take an m by n totally L-matrix as such a matrix A. If n > m + 2, there exists
an m by m + 2 totally L-matrix Tn−m−2 with n − m − 2 single-extensions. Hence
there exists an m by n matrix A ∈ Tn−m−2 which contains Tn−m−2 by the remark
above.
Acknowledgment. We would like to thank the referees for their comments.
REFERENCES
[1] R. A. Brualdi and B. L. Shader, The Matrices of Sign-Solvable Linear Systems, Cambridge
University Press, Cambridge, UK, 1995.
[2] K. G. Fisher, W. Morris, and J. Shapiro, Mixed dominating matrices, Linear Algebra Appl.,
270 (1998), pp. 191–214.
[3] S.-J. Kim and B. L. Shader, Linear systems with signed solutions, Linear Algebra Appl., 313
(2000), pp. 21–40.
[4] S.-J. Kim and B. L. Shader, On matrices which have signed null-spaces, Linear Algebra Appl.,
353 (2002), pp. 245–255.