Orthogonal realizations of random sign patterns and other applications of the SIPP

Zachary Brennan Department of Mathematics, Iowa State University (brennanz, cocox, bcurtis1, enriqueg, kph3, hogben, conorjt)@iastate.edu Christopher Cox²²footnotemark: 2 Bryan A. Curtis²²footnotemark: 2 Corresponding author Enrique Gomez-Leos²²footnotemark: 2 Kimberly P. Hadaway²²footnotemark: 2 Leslie Hogben²²footnotemark: 2 American Institute of Mathematics, San Jose, CA 95112, USA ([email protected]). Conor Thompson²²footnotemark: 2

Abstract

A sign pattern is an array with entries in $\{+,-,0\}$ . A matrix $Q$ is row orthogonal if $QQ^{T}=I$ . The Strong Inner Product Property (SIPP), introduced in [B.A. Curtis and B.L. Shader, Sign patterns of orthogonal matrices and the strong inner product property, Linear Algebra Appl. 592: 228–259, 2020], is an important tool when determining whether a sign pattern allows row orthogonality because it guarantees there is a nearby matrix with the same property, allowing zero entries to be perturbed to nonzero entries, while preserving the sign of every nonzero entry. This paper uses the SIPP to initiate the study of conditions under which random sign patterns allow row orthogonality with high probability. Building on prior work, $5\times n$ nowhere zero sign patterns that minimally allow orthogonality are determined. Conditions on zero entries in a sign pattern are established that guarantee any row orthogonal matrix with such a sign pattern has the SIPP.

keywords:

Sign pattern, Orthogonality, Row orthogonal matrix, Strong Inner Product Property, SIPP, Random matrix, High probability.

{AMS}

15B10, 15B35, 15B52, 60B20.

1 Introduction

A sign pattern is an array with entries coming from the set $\{+,-,0\}$ . The entries of sign patterns encode qualitative properties of real matrices. Sign patterns were introduced in applications where the entries of the matrix may be known only approximately (or not at all), but the signs of the entries are known. A matrix $Q$ is row orthogonal provided $QQ^{T}=I$ . The problem of determining whether an $m\times n$ sign pattern allows row orthogonality has been studied for many years [7, 10, 6, 5]. Recently the strong inner product property (SIPP) was introduced by Curtis and Shader in [6] to study sign patterns of row orthogonal matrices. This paper relies heavily on the SIPP to build on prior work (e.g., classifying small patterns that minimally allow orthogonality) and initiate the study of conditions under which random sign patterns allow row orthogonality with high probability.

Finding a certificate that a sign pattern allows row orthogonality is often difficult. By applying a variant of Gram-Schmidt orthogonalization to a nowhere zero nearly row orthogonal matrix we obtain conditions that guarantee the existence of a nearby row orthogonal matrix with the same sign pattern (see Section 2). In Section 3, we apply the SIPP to develop new tools to show that a sign pattern allows row orthogonality and use these tools (and the results from Section 2) to determine $5\times n$ nowhere zero sign patterns that minimally allow orthogonality. We also establish conditions on zero entries in a sign pattern that guarantee any row orthogonal matrix with such a sign pattern has the SIPP. One of our main results, Theorem 4.12, utilizes the SIPP to obtain a lower bound $h(m)$ such that the probability of a random $m\times n$ sign pattern allowing row orthogonality goes to $1$ as $m$ tends toward $\infty$ for $n\geq h(m)$ (here random means $+$ and $-$ are equally likely and the probability of $0$ is given). The remainder of this introduction defines terminology and notation (Section 1.1) and lists known results we will use (Section 1.2).

1.1 Definitions and notation

In the study of sign patterns, sometimes the distinction between zero and nonzero is more important than the sign. A zero-nonzero pattern or znz pattern is an array with entries coming from the set $\{*,0\}$ . We use the term pattern to mean a sign pattern or a zero-nonzero pattern. Given a real number $a$ ,

\operatorname{sgn}(a)=\begin{cases}+&\text{if }a>0\\ -&\text{if }a<0\\ 0&\text{if }a=0\end{cases}\qquad\text{and}\qquad\operatorname{znz}(a)=\begin{cases}*&\text{if }a\not=0\\ 0&\text{if }a=0.\end{cases}

The sign pattern and zero-nonzero pattern of a matrix $A=[a_{ij}]$ are $\operatorname{sgn}(A)=[\operatorname{sgn}(a_{ij})]$ and $\operatorname{znz}(A)=[\operatorname{znz}(a_{ij})]$ , respectively. The qualitative class of an $m\times n$ sign pattern $S$ is the set

\mathcal{Q}(S)=\{A\in\mathbb{R}^{m\times n}:\operatorname{sgn}(A)=S\},

and the qualitative class of an $m\times n$ znz pattern $Z=[z_{ij}]$ is the set

\mathcal{Q}(Z)=\{A\in\mathbb{R}^{m\times n}:\operatorname{znz}(A)=Z\}.

A matrix in the qualitative class $\mathcal{Q}(P)$ is called a realization of the pattern $P$ . For a sign pattern $S$ , $C_{S}$ denotes the unique $(1,-1,0)$ -matrix that is a realization of the sign pattern $S$ . Similarly, $C_{Z}$ is the unique $(1,0)$ -matrix that is a realization of the zero-nonzero pattern $Z$ . A superpattern of a sign pattern $S=[s_{ij}]$ is a sign pattern $R=[r_{ij}]$ of the same dimensions such that $r_{ij}=s_{ij}$ whenever $s_{ij}\in\{+,-\}$ ; if $s_{ij}=0$ then $r_{ij}\in\{+,-,0\}$ .

A matrix with orthogonal rows is not necessarily row orthogonal; for us, the rows of a row orthogonal matrix have unit length. The set of $m\times n$ row orthogonal matrices is denoted by $\mathcal{O}(m,n)$ and we write $\mathcal{O}(m)$ as shorthand for $\mathcal{O}(m,m)$ . Note that every matrix $Q\in\mathcal{O}(m)$ is orthogonal, i.e., $Q^{T}Q=QQ^{T}=I$ . The set of $m\times m$ real symmetric matrices is denoted by $\operatorname{sym}(m)$ .

A zero matrix $O\in\mathbb{R}^{m\times n}$ or zero vector ${\bf 0}\in\mathbb{R}^{n}$ has every entry equal to zero. An $m\times n$ matrix or pattern is wide if $m\leq n$ . A wide matrix has full rank if its rank equals its number of rows, i.e., it has linearly independent rows. A row orthogonal matrix is necessarily wide. Let $A\in\mathbb{R}^{m\times n}$ be a wide matrix. Then $A$ has the strong inner product property (SIPP) provided $X=O$ is the only symmetric matrix satisfying $(XA)\circ A=O$ [5]. The strong inner product property is one of a number of strong properties of matrices that guarantee there is a nearby matrix with the same property, allowing zero entries to be perturbed to nonzero entries, while preserving the sign of every nonzero entry [8, Part 2].

An $m\times n$ sign pattern $S$ allows row orthogonality if there is a row orthogonal matrix $Q\in\mathcal{Q}(S)$ (equivalently, $\mathcal{O}(m,n)\cap\mathcal{Q}(S)\neq\emptyset$ ). An $m\times n$ sign pattern $S$ allows o-SIPP if there is a row orthogonal matrix $Q\in\mathcal{Q}(S)$ that has the SIPP. Since scaling a matrix with a positive constant does not change its pattern, no pattern requires row orthogonality. A sign pattern $S$ requires o-SIPP if every $Q\in\mathcal{Q}(S)\cap\mathcal{O}(m,n)$ has the SIPP and $\mathcal{Q}(S)\cap\mathcal{O}(m,n)\neq\emptyset$ . Without the assumption that $\mathcal{Q}(S)\cap\mathcal{O}(m,n)\neq\emptyset$ , the all zeros pattern would vacuously require o-SIPP.

An $m\times n$ rectangular sign pattern $S$ is row potentially pairwise-orthogonal or row PPO if no row is a zero vector and for each pair $(i,k)$ with $1\leq i<k\leq m$ , there are realizations of row $i$ and row $k$ that are orthogonal. The term column PPO is defined analogously. A pair of rows $i$ and $k$ in a $m\times n$ rectangular sign pattern $S=[s_{ij}]$ has a negative $4$ -cycle if there are two columns $j$ and $\ell$ such that $s_{ij}s_{kl}=+$ and $s_{ij}s_{kl}=-$ , where multiplication on the set $\{0,+,-\}$ is defined in the obvious way that conforms to real arithmetic. A pair of rows $i$ and $k$ in an $m\times n$ matrix or pattern $P=[p_{ij}]$ is combinatorially orthogonal if $p_{ij}\neq 0$ implies $p_{kj}=0$ for every $j=1,\dots,n$ .

A signed permutation matrix is a square $(1,-1,0)$ -matrix with exactly one nonzero entry in each row and column. Matrices $A,B\in\mathbb{R}^{m\times n}$ are sign equivalent if $A=P_{1}BP_{2}$ , where $P_{1}$ and $P_{2}$ are signed permutation matrices. Two sign patterns $S$ and $S^{\prime}$ are sign equivalent if $C_{S}$ and $C_{S^{\prime}}$ are sign equivalent.

For a vector ${\bf v}\in\mathbb{R}^{n}$ , the support of ${\bf v}$ , denoted by $\operatorname*{supp}({\bf v})$ , is the set of indices of nonzero entries of ${\bf v}$ . Let $[n]=\{1,\dots,n\}$ .

1.2 Known results

In the remainder of this introduction we provide some known results about the SIPP that we will use. The primary motivation for developing the SIPP is given by the next theorem of Curtis and Shader.¹¹1Theorem 4.5 in [6] actually says that every superpattern of $S$ allows row orthogonality, but the proof shows it allows o-SIPP. We provide a slightly stronger result in Theorem 3.13.

Theorem 1.1.

[6] If $Q\in\mathcal{O}(m,n)$ has the SIPP and $\operatorname{sgn}(Q)=S$ , then every superpattern of $S$ allows o-SIPP.

Theorem 1.1 has many consequences. Here we list some that we use. A matrix with the SIPP or a sign pattern that allows the SIPP can be padded with additional zero columns and retain that property.

Lemma 1.2.

[6] Let $A\in\mathbb{R}^{m\times n}$ and $p>n$ . Then $A$ has the SIPP if and only if the $m\times p$ matrix $B=\big{[}A\leavevmode\nobreak\ |\leavevmode\nobreak\ O\big{]}$ has the SIPP.

Corollary 1.3.

[6] If $Q\in\mathcal{O}(m,n)$ has the SIPP and $\operatorname{sgn}(Q)=S$ , then $\begin{bmatrix}{S\leavevmode\nobreak\ \big{|}\leavevmode\nobreak\ O}\end{bmatrix}$ allows o-SIPP.

The next two results show that sign equivalence preserves having the SIPP, as does taking the transpose for (square) orthogonal matrices.

Proposition 1.4.

[6] Let $A,B\in\mathbb{R}^{m\times n}$ be sign equivalent. Then $A$ has the SIPP if and only if $B$ has the SIPP.

Proposition 1.5.

[6] Let $Q\in\mathcal{O}(m)$ . Then $Q$ has the SIPP if and only if $Q^{T}$ has the SIPP.

The previous results provide some sufficient conditions for a sign pattern to allow row orthogonality. The next result provides a way to show a sign pattern does not allow row orthogonality.

Theorem 1.6.

[10] Let $S$ be a nowhere zero sign pattern and let $R$ be an $r\times s$ submatrix of $S$ . If $r+s\geq n+2$ and $\operatorname{rank}C_{R}=1$ , then $S$ does not allow row orthogonality.

2 From approximate orthogonality to exact orthogonality

In this section, we establish a result that gives conditions under which a collection of “nearly” orthogonal vectors necessarily implies the existence of a “nearby” collection of truly orthogonal vectors. Such a result is similar in spirit to the effective implicit function theorems used by, e.g., Cohn, Kumar and Minton [4] to derive the existence of an exact code from an approximate one. However, instead of using an implicit function theorem, we simply rely on the Gram–Schmidt process. Although the perturbations here are created by a different mechanism, we also point out that the idea of perturbing one solution to obtain another desired solution is a fundamental idea underlying strong properties. First, we define the function $r_{m}(\epsilon)$ used to quantify the notion of “nearby.”

Definition 2.1.

For an integer $m\geq 1$ and a real number $0\leq\epsilon<\frac{1}{m-1}$ ,

r_{m}(\epsilon)=\sqrt{{1+\epsilon\over(1-(m-2)\epsilon)(1-(m-1)\epsilon)}}-1

where $\frac{1}{0}$ is interpreted as $\infty$ , so $r_{1}(\epsilon)=0$ for all $\epsilon\geq 0$ .

For simplicity, we have defined the functions $r_{m}(\epsilon)$ in closed form. In order to use these functions for the results of this section we need a recursive approach, which is given in the next lemma.

Lemma 2.2.

Given $r_{1}(\epsilon)=0$ , $r_{m}(\epsilon)$ can be computed recursively for all $m\geq 2$ and all $0\leq\epsilon<\frac{1}{m-1}$ by

r_{m}(\epsilon)=\sqrt{\frac{1+\epsilon}{1-\epsilon}}\biggl{(}r_{m-1}\biggl{(}\frac{\epsilon}{1-\epsilon}\biggr{)}+1\biggr{)}-1.

Proof 2.3.

It is easy to verify the result for $m=2$ . For $m\geq 3$ ,

	$\displaystyle r_{m}(\epsilon)$	$\displaystyle=\sqrt{{1+\epsilon\over(1-(m-2)\epsilon)(1-(m-1)\epsilon)}}-1.$
		$\displaystyle=\sqrt{{1+\epsilon\over 1-\epsilon}}\sqrt{{(1-\epsilon)((1-\epsilon)+\epsilon)\over\bigl{(}(1-\epsilon)-(m-3)\epsilon\bigr{)}\bigl{(}(1-\epsilon)-(m-2)\epsilon\bigr{)}}}-1$
		$\displaystyle=\sqrt{{1+\epsilon\over 1-\epsilon}}\sqrt{{1+{\epsilon\over 1-\epsilon}\over\bigl{(}1-(m-3){\epsilon\over 1-\epsilon}\bigr{)}\bigl{(}1-(m-2){\epsilon\over 1-\epsilon}\bigr{)}}}-1$
		$\displaystyle=\sqrt{{1+\epsilon\over 1-\epsilon}}\biggl{(}r_{m-1}\biggl{(}{\epsilon\over 1-\epsilon}\biggr{)}+1\biggr{)}-1.$

The next lemma provides the key step to go from approximately to exactly orthogonal.

Lemma 2.4.

Let $m$ be a positive integer, let $0\leq\epsilon<{1\over m-1}$ and fix any inner product space $(\Omega,\langle\cdot,\cdot\rangle)$ . Additionally, let $\lVert\cdot\rVert$ be any norm on $\Omega$ (possibly unrelated to $\langle\cdot,\cdot\rangle$ ). If ${\bf x}_{1},\dots,{\bf x}_{m}\in\Omega$ satisfy

1.

$\langle{\bf x}_{i},{\bf x}_{i}\rangle=1$ for all $i\in[m]$ , and
2.

$\lvert\langle{\bf x}_{i},{\bf x}_{j}\rangle\rvert\leq\epsilon$ for all $i\neq j\in[m]$ ,

then there exists $\widetilde{{\bf x}}_{1},\dots,\widetilde{{\bf x}}_{m}\in\operatorname*{span}\{{\bf x}_{1},\dots,{\bf x}_{m}\}$ satisfying

1.

$\{\widetilde{{\bf x}}_{1},\dots,\widetilde{{\bf x}}_{m}\}$ is orthonormal with respect to $\langle\cdot,\cdot\rangle$ , and
2.

$\lVert{\bf x}_{i}-\widetilde{{\bf x}}_{i}\rVert\leq r_{m}(\epsilon)\lVert{\bf x}_{i}\rVert$ for all $i\in[m]$ .

Proof 2.5.

We prove the result by induction on $m$ . The case $m=1$ is immediate by taking $\widetilde{{\bf x}}_{1}={\bf x}_{1}$ . Let $m\geq 2$ be a positive integer and suppose the statement holds for $m-1$ .

Without loss of generality, $\lVert{\bf x}_{m}\rVert\leq\lVert{\bf x}_{i}\rVert$ for all $i\in\{1,\dots,m\}$ . For $i\in\{1,\ldots,m-1\}$ , let ${\bf x}_{i}^{\mkern 3.0mu\vphantom{\perp}\vrule depth=0.0pt\mkern 4.0mu\vrule depth=0.0pt\mkern 3.0mu}=\langle{\bf x}_{i},{\bf x}_{m}\rangle{\bf x}_{m}$ and ${\bf x}_{i}^{\perp}={\bf x}_{i}-{\bf x}_{i}^{\mkern 3.0mu\vphantom{\perp}\vrule depth=0.0pt\mkern 4.0mu\vrule depth=0.0pt\mkern 3.0mu}$ ; then $\langle{\bf x}_{i}^{\perp},{\bf x}_{m}\rangle=0$ . Since $\lvert\langle{\bf x}_{i},{\bf x}_{m}\rangle\rvert\leq\epsilon$ and $\langle{\bf x}_{m},{\bf x}_{m}\rangle=1$ , we know that $0\leq\langle{\bf x}_{i}^{\mkern 3.0mu\vphantom{\perp}\vrule depth=0.0pt\mkern 4.0mu\vrule depth=0.0pt\mkern 3.0mu},{\bf x}_{i}^{\mkern 3.0mu\vphantom{\perp}\vrule depth=0.0pt\mkern 4.0mu\vrule depth=0.0pt\mkern 3.0mu}\rangle\leq\epsilon^{2}$ . Therefore, the Pythagorean Theorem allows us to conclude that

(2.1)

\langle{\bf x}_{i},{\bf x}_{i}\rangle=\langle{\bf x}_{i}^{\mkern 3.0mu\vphantom{\perp}\vrule depth=0.0pt\mkern 4.0mu\vrule depth=0.0pt\mkern 3.0mu},{\bf x}_{i}^{\mkern 3.0mu\vphantom{\perp}\vrule depth=0.0pt\mkern 4.0mu\vrule depth=0.0pt\mkern 3.0mu}\rangle+\langle{\bf x}_{i}^{\perp},{\bf x}_{i}^{\perp}\rangle\quad\implies\quad 1\geq\langle{\bf x}_{i}^{\perp},{\bf x}_{i}^{\perp}\rangle\geq 1-\epsilon^{2}.

Since $\epsilon<1$ , we know that ${\bf x}_{i}^{\perp}$ is non-zero. Let $\widehat{{\bf x}}_{i}^{\perp}$ denote the unit vector in the direction of ${\bf x}_{i}^{\perp}$ , i.e., $\widehat{{\bf x}}_{i}^{\perp}=\frac{1}{\sqrt{\langle{\bf x}_{i}^{\perp},{\bf x}_{i}^{\perp}\rangle}}{\bf x}_{i}^{\perp}$ .

Since ${\bf x}_{i}^{\mkern 3.0mu\vphantom{\perp}\vrule depth=0.0pt\mkern 4.0mu\vrule depth=0.0pt\mkern 3.0mu}=\langle{\bf x}_{i},{\bf x}_{m}\rangle{\bf x}_{m}$ , we see that $\lVert{\bf x}_{i}^{\mkern 3.0mu\vphantom{\perp}\vrule depth=0.0pt\mkern 4.0mu\vrule depth=0.0pt\mkern 3.0mu}\rVert\leq\epsilon\lVert{\bf x}_{m}\rVert\leq\epsilon\lVert{\bf x}_{i}\rVert$ . Then the triangle inequality applied to ${\bf x}_{i}^{\perp}={\bf x}_{i}+(-{\bf x}_{i}^{\mkern 3.0mu\vphantom{\perp}\vrule depth=0.0pt\mkern 4.0mu\vrule depth=0.0pt\mkern 3.0mu})$ implies that $\lVert{\bf x}_{i}^{\perp}\rVert\leq(1+\epsilon)\lVert{\bf x}_{i}\rVert$ . Together with (2.1), we have

(2.2)

\lVert\widehat{{\bf x}}_{i}^{\perp}\rVert\leq\frac{1+\epsilon}{\sqrt{1-\epsilon^{2}}}\lVert{\bf x}_{i}\rVert=\sqrt{{1+\epsilon\over 1-\epsilon}}\lVert{\bf x}_{i}\rVert.

In particular,

(2.3)		$\displaystyle\lVert{\bf x}_{i}-\widehat{{\bf x}}_{i}^{\perp}\rVert$	$\displaystyle\leq$	$\displaystyle\lVert{\bf x}_{i}^{\mkern 3.0mu\vphantom{\perp}\vrule depth=0.0pt\mkern 4.0mu\vrule depth=0.0pt\mkern 3.0mu}\rVert+\lVert{\bf x}_{i}^{\perp}-\widehat{{\bf x}}_{i}^{\perp}\rVert=\lVert{\bf x}_{i}^{\mkern 3.0mu\vphantom{\perp}\vrule depth=0.0pt\mkern 4.0mu\vrule depth=0.0pt\mkern 3.0mu}\rVert+\biggl{(}{1\over\sqrt{\langle{\bf x}_{i}^{\perp},{\bf x}_{i}^{\perp}\rangle}}-1\biggr{)}\lVert{\bf x}_{i}^{\perp}\rVert$
(2.3)			$\displaystyle\leq$	$\displaystyle\epsilon\lVert{\bf x}_{i}\rVert+\biggl{(}{1\over\sqrt{1-\epsilon^{2}}}-1\biggr{)}(1+\epsilon)\lVert{\bf x}_{i}\rVert=\biggl{(}\sqrt{\frac{1+\epsilon}{1-\epsilon}}-1\biggr{)}\lVert{\bf x}_{i}\rVert,$

where the second inequality follows by combining (2.1) and $\lVert{\bf x}_{i}^{\perp}\rVert\leq(1+\epsilon)\lVert{\bf x}_{i}\rVert$ .

Now, for any other $j\in\{1,\ldots,m-1\}$ with $j\neq i$ , we have

$\displaystyle\langle{\bf x}_{i}^{\perp},{\bf x}_{j}^{\perp}\rangle$	$\displaystyle=$	$\displaystyle\langle{\bf x}_{i},{\bf x}_{j}\rangle-\langle{\bf x}_{i},{\bf x}_{m}\rangle\langle{\bf x}_{m},{\bf x}_{j}\rangle$
$\displaystyle\implies\lvert\langle{\bf x}_{i}^{\perp},{\bf x}_{j}^{\perp}\rangle\rvert$	$\displaystyle\leq$	$\displaystyle\epsilon+\epsilon^{2}$
$\displaystyle\implies\lvert\langle\widehat{{\bf x}}_{i}^{\perp},\widehat{{\bf x}}_{j}^{\perp}\rangle\rvert$	$\displaystyle\leq$	$\displaystyle{\epsilon+\epsilon^{2}\over\sqrt{\langle{\bf x}_{i}^{\perp},{\bf x}_{i}^{\perp}\rangle\langle{\bf x}_{j}^{\perp},{\bf x}_{j}^{\perp}\rangle}}\leq\frac{\epsilon+\epsilon^{2}}{1-\epsilon^{2}}=\frac{\epsilon}{1-\epsilon}.$

Therefore, since $\widehat{{\bf x}}_{1}^{\perp},\dots,\widehat{{\bf x}}_{m-1}^{\perp}$ are unit vectors by construction, we may apply the induction hypothesis to find an orthonormal set $\{\widetilde{{\bf x}}_{1},\dots,\widetilde{{\bf x}}_{m-1}\}\subseteq\operatorname*{span}\{\widehat{{\bf x}}_{1}^{\perp},\dots,\widehat{{\bf x}}_{m-1}^{\perp}\}$ such that

\lVert\widehat{{\bf x}}_{i}^{\perp}-\widetilde{{\bf x}}_{i}\rVert\leq r_{m-1}\biggl{(}\frac{\epsilon}{1-\epsilon}\biggr{)}\lVert\widehat{{\bf x}}_{i}^{\perp}\rVert

for each $i\in\{1,\ldots,m-1\}$ . By invoking additionally (2.2) and (2.3), we bound

	$\displaystyle\lVert{\bf x}_{i}-\widetilde{{\bf x}}_{i}\rVert$	$\displaystyle\leq\lVert{\bf x}_{i}-\widehat{{\bf x}}_{i}^{\perp}\rVert+\lVert\widehat{{\bf x}}_{i}^{\perp}-\widetilde{{\bf x}}_{i}\rVert\leq\biggl{(}\sqrt{{1+\epsilon\over 1-\epsilon}}-1\biggr{)}\lVert{\bf x}_{i}\rVert+r_{m-1}\biggl{(}{\epsilon\over 1-\epsilon}\biggr{)}\lVert\widehat{{\bf x}}_{i}^{\perp}\rVert$
		$\displaystyle\leq\biggl{(}\sqrt{{1+\epsilon\over 1-\epsilon}}-1+\sqrt{{1+\epsilon\over 1-\epsilon}}r_{m-1}\biggl{(}{\epsilon\over 1-\epsilon}\biggr{)}\biggr{)}\lVert{\bf x}_{i}\rVert=r_{m}(\epsilon)\lVert{\bf x}_{i}\rVert$

for all $i\in\{1,\ldots,m-1\}$ where the last equality follows from Lemma 2.2.

Finally, let $\widetilde{{\bf x}}_{m}={\bf x}_{m}$ . Then $\widetilde{{\bf x}}_{1},\dots,\widetilde{{\bf x}}_{m}$ satisfy the claim, because $\widetilde{{\bf x}}_{1},\dots,\widetilde{{\bf x}}_{m-1}\in\break\operatorname*{span}\{\widehat{{\bf x}}_{1}^{\perp},\dots,\widehat{{\bf x}}_{m-1}^{\perp}\}\subseteq\operatorname*{span}\{{\bf x}_{1},\dots,{\bf x}_{m}\}$ by construction, and the former subspace is orthogonal to ${\bf x}_{m}=\widetilde{{\bf x}}_{m}$ .

Observe that the process used to create the vectors $\widetilde{{\bf x}}_{i}$ is a reordering of the modified Gram-Schmit process. We stated Lemma 2.4 very generally in the hopes that other researchers will find it useful; for our uses, we specialize to the standard Euclidean inner product and the $\infty$ -norm to attain a result related to row orthogonal realizations.

We apply Lemma 2.4 to obtain Theorem 2.7, which will be used in Section 3.3 to characterize $5\times n$ nowhere zero sign patterns that minimally allow orthogonality. Essentially this result says that for any matrix that is close to being row orthogonal, there exists a nearby matrix that is row orthogonal and has the same sign pattern.

Definition 2.6.

For a non-zero vector ${\bf x}=[x_{1},\dots,x_{n}]^{T}\in\mathbb{R}^{n}$ , define

\delta({\bf x})={\min_{i\in[n]}\lvert x_{i}\rvert\over\max_{j\in[n]}\lvert x_{j}\rvert}={\min_{i\in[n]}\lvert x_{i}\rvert\over\lVert{\bf x}\rVert_{\infty}}.

Theorem 2.7.

Let ${\bf x}_{1},\dots,{\bf x}_{m}\in\mathbb{R}^{n}$ be any non-zero vectors and let $\epsilon=\max_{i\neq j}\big{\lvert}\big{\langle}{{\bf x}_{i}\over\lVert{\bf x}_{i}\rVert_{2}},{{\bf x}_{j}\over\lVert{\bf x}_{j}\rVert_{2}}\big{\rangle}\big{\rvert},$ where $\langle\cdot,\cdot\rangle$ is the standard Euclidean inner product. If

1.

$\epsilon<{1\over m-1}$ , and
2.

$r_{m}(\epsilon)<\min_{i\in[m]}\delta({\bf x}_{i})$ ,

then there exists an orthogonal set $\{\widetilde{{\bf x}}_{1},\dots,\widetilde{{\bf x}}_{m}\}\subseteq\mathbb{R}^{n}$ satisfying $\operatorname{sgn}({\bf x}_{i})=\operatorname{sgn}(\widetilde{{\bf x}}_{i})$ for all $i\in[m]$ .

Proof 2.8.

We apply Lemma 2.4 to the vectors $\frac{1}{\|{\bf x}_{i}\|_{2}}{\bf x}_{i}$ , specializing to the Euclidean inner product and the $\infty$ -norm, to locate an orthonormal set $\{\widetilde{{\bf x}}_{1}^{\prime},\dots,\widetilde{{\bf x}}_{m}^{\prime}\}\subseteq\mathbb{R}^{n}$ such that

\biggl{\lVert}{{\bf x}_{i}\over\lVert{\bf x}_{i}\rVert_{2}}-\widetilde{{\bf x}}_{i}^{\prime}\biggr{\rVert}_{\infty}\leq r_{m}(\epsilon)\biggl{\lVert}{{\bf x}_{i}\over\lVert{\bf x}_{i}\rVert_{2}}\biggr{\rVert}_{\infty}\quad\implies\quad\lVert{\bf x}_{i}-\lVert{\bf x}_{i}\rVert_{2}\cdot\widetilde{{\bf x}}_{i}^{\prime}\rVert_{\infty}\leq r_{m}(\epsilon)\lVert{\bf x}_{i}\rVert_{\infty}

for all $i\in[m]$ . In particular, setting $\widetilde{{\bf x}}_{i}=\lVert{\bf x}_{i}\rVert_{2}\cdot\widetilde{{\bf x}}_{i}^{\prime}$ for each $i\in[m]$ , we know that $\{\widetilde{{\bf x}}_{1},\dots,\widetilde{{\bf x}}_{m}\}$ is an orthogonal set and that

\lVert{\bf x}_{i}-\widetilde{{\bf x}}_{i}\rVert_{\infty}\leq r_{m}(\epsilon)\lVert{\bf x}_{i}\rVert_{\infty}<\delta({\bf x}_{i})\lVert{\bf x}_{i}\rVert_{\infty}=\min_{j\in[n]}\lvert({\bf x}_{i})_{j}\rvert.

Since $\lvert x-y\rvert<\lvert x\rvert\implies\operatorname{sgn}(x)=\operatorname{sgn}(y)$ for any $x,y\in\mathbb{R}$ , we conclude that $\operatorname{sgn}({\bf x}_{i})=\operatorname{sgn}(\widetilde{{\bf x}}_{i})$ for all $i\in[m]$ .

One particularly useful feature of Theorem 2.7 is that it can be used to present reasonable certificates of the existence of row orthogonal realizations; in fact, it implies that integer-valued certificates can always be found. We illustrate this in the following example (which will be used in Section 3.3).

Example 2.9.

Consider the sign-pattern

S=\begin{bmatrix}-&-&-&+&+&+\\ +&+&-&+&+&+\\ +&+&+&-&-&+\\ +&+&+&+&+&-\\ +&+&+&+&+&+\end{bmatrix}.

Explicitly writing down a row orthogonal realization of $S$ would be difficult since this requires exact arithmetic. Despite this, it is not too difficult for a computer to find realizations of $S$ that are row orthogonal up to floating-point error. For example, the following matrix is such a realization for $S$ :

A^{\prime}=\begin{bmatrix}-0.0743294&-0.668965&-0.222988&0.371647&0.0743294&0.594635\\ 0.118415&0.59468&-0.665382&0.0360018&0.195624&0.387344\\ 0.511869&0.0620542&0.206774&-0.259068&-0.646593&0.454076\\ 0.665978&0.0389929&0.0396191&0.681063&0.0657504&-0.291912\\ 0.02319&0.264691&0.660817&0.0611589&0.541388&0.442585\\ \end{bmatrix}.

Of course, $A^{\prime}$ is not actually a row orthogonal matrix and so it does not directly demonstrate that $S$ has a row orthogonal realization; however, $A^{\prime}$ does satisfy the hypotheses of Theorem 2.7. In fact, by scaling and truncating $A^{\prime}$ appropriately, we find the following integer-valued matrix which satisfies the hypotheses of Theorem 2.7 as well:

A=\begin{bmatrix}-8&-74&-25&41&8&65\\ 13&65&-73&4&22&43\\ 56&7&23&-28&-71&50\\ 73&4&4&75&7&-32\\ 3&29&73&7&60&49\end{bmatrix}.

Here and in similar examples, we use $\delta$ to denote $\min_{i\in[m]}\delta({\bf r}_{i})$ where the ${\bf r}_{i}$ are the rows of the matrix. To apply Theorem 2.7 to the matrix $A$ , observe that the value $\delta=\frac{3}{73}>.004$ is obtained from row $5$ of $A$ and the value $\epsilon={71\over\sqrt{146335965}}<0.006$ is obtained from rows $1$ and $4$ . Since $r_{5}$ is increasing on its domain, $r_{5}(\epsilon)<r_{5}(0.006)<0.03<\delta$ . We may therefore apply Theorem 2.7 to conclude that there exists a row orthogonal matrix with the same sign-pattern as $A$ .

We will use these same basic ideas in Section 3.3 to write down reasonable certificates for the existence of row orthogonal realizations for other sign patterns.

3 Results on the SIPP

In this section we present results related to the SIPP and orthogonality. Section 3.1 contains some useful tools for studying matrices that have the SIPP. Of particular interest is Theorem 3.13 which extends Theorem 1.1. In Section 3.2 we investigate sign patterns that require o-SIPP. Section 3.3 utilizes the SIPP to provide a complete characterization of nowhere zero $m\times n$ sign patterns that minimally allow orthogonality for $m\leq 5$ .

3.1 Tools

Recall that an $m\times n$ matrix $A$ has the SIPP provided $O$ is the only symmetric matrix $X$ satisfying $(XA)\circ A=O$ . It is often much easier to construct a matrix with orthogonal rows as opposed to a row orthogonal matrix. The next lemma allows us to study row orthogonal matrices with the SIPP without first normalizing the rows.

Lemma 3.1.

Suppose $Q$ is an $m\times n$ full rank matrix with orthogonal rows that has the SIPP and $D$ is any $m\times m$ diagonal matrix with every diagonal entry nonzero. Then $DQ$ has the SIPP. Furthermore, $D$ can be chosen so that $DQ$ is row orthogonal.

Proof 3.2.

Let $X\in\operatorname{sym}(m)$ such that $(XDQ)\circ(DQ)=O$ . By algebraic manipulation,

O=(XDQ)\circ(DQ)=(DXD)Q\circ Q.

Since $DXD\in\operatorname{sym}(m)$ and $Q$ has the SIPP, it follows that $DXD=O$ , which implies $X=O$ . Thus $DQ$ has the SIPP. Let ${\bf r}_{i}^{T}$ denote the $i$ th row of $Q$ . Define $D=\operatorname{diag}\left(\frac{1}{\|{\bf r}_{1}\|},\dots,\frac{1}{\|{\bf r}_{m}\|}\right)$ and $\widehat{Q}=DQ$ , so $\widehat{Q}\in\mathcal{O}(m,n)$ .

The next three lemmas showcase additional hypotheses on $A$ that imply various entries in $X$ are $0$ .

Lemma 3.3.

Let $A\in\mathbb{R}^{m\times n}$ be a wide matrix with full rank and let $X\in\mathbb{R}^{m\times n}$ . Suppose that every entry of row $k$ of $A$ is nonzero. If $(XA)\circ A=O$ , then every entry of row $k$ of $X$ is zero.

Proof 3.4.

Suppose $(XA)\circ A=O$ . Let ${\bf r}_{1}^{T},\dots,{\bf r}_{m}^{T}$ denote the rows of $X$ . Then $(XA)\circ A=O$ implies that ${\bf r}_{k}^{T}A={\bf 0}^{T}$ . Since $A$ has full rank there exists a matrix $B$ such that $AB=I$ and so ${\bf 0}^{T}={\bf r}_{k}^{T}AB={\bf r}_{k}^{T}$ .

Lemma 3.5.

Suppose $Q\in\mathcal{O}(m,n)$ , $X\in\operatorname{sym}(m)$ and $(XQ)\circ Q=O$ . Then $I\circ X=O$ .

Proof 3.6.

Let $Y=XQ$ and write $Y=[y_{ij}]$ , $X=[x_{ij}]$ , and $Q=[q_{ij}]$ . Since $Q$ is row orthogonal, $X=YQ^{T}$ . The condition that $(XQ)\circ Q=O$ implies that $y_{ij}=0$ if $q_{ij}\not=0$ . Therefore,

x_{ii}=(YQ^{T})_{ii}=\sum_{j=1}^{m}y_{ij}q_{ij}=0.

In other words, $I\circ X=O$ .

Lemma 3.7.

Let $Q=[q_{ij}]\in\mathcal{O}(m,n)$ and $X=[x_{ij}]\in\operatorname{sym}(m)$ satisfy the equation $(XQ)\circ Q=O$ . Suppose that the only two nonzero entries in column $j$ of $Q$ are $q_{ij}$ and $q_{kj}$ . Then $x_{ik}=x_{ki}=0$ .

Proof 3.8.

Since $(XQ)\circ Q=O$ ,

0=((XQ)\circ Q)_{ij}=\left(\sum_{\ell=1}^{m}x_{i\ell}q_{\ell j}\right)q_{ij}=(x_{ii}q_{ij}+x_{ik}q_{kj})q_{ij}.

Since $q_{ij}\neq 0$ , $x_{ii}q_{ij}+x_{ik}q_{kj}=0$ . By Lemma 3.5, $x_{ii}=0$ , so $x_{ik}q_{kj}=0$ . Since $q_{kj}\neq 0$ , $x_{ik}=0$ .

The next result extends one direction of [6, Proposition 3.9].

Lemma 3.9.

Suppose $A$ is a wide matrix partitioned as a $2\times 2$ block matrix $A=\left[\begin{array}[]{c|c}A_{1}&A_{2}\\ \hline\cr A_{3}&A_{4}\\ \end{array}\right]$ with $A_{3},A_{4}$ both nowhere zero (or vacuous). If $A_{1}$ has the SIPP and $A$ is full rank, then $A$ has the SIPP.

Proof 3.10.

Let $X=\left[\begin{array}[]{c|c}X_{1}&X_{2}\\ \hline\cr X_{2}^{T}&X_{4}\end{array}\right]$ be a symmetric matrix such that $(XA)\circ A=O$ . By Lemma 3.3, $\left[\begin{array}[]{c|c}X_{2}^{T}&X_{4}\end{array}\right]=O$ . Therefore, $X=\left[\begin{array}[]{c|c}X_{1}&O\\ \hline\cr O&O\end{array}\right]$ . The equation $(XA)\circ A=O$ implies that $(X_{1}A_{1})\circ A_{1}=O$ . Since $X_{1}$ is symmetric and $A_{1}$ has the SIPP, $X_{1}=O$ and $A$ has the SIPP.

Manifold theory, and in particular having manifolds interesect transversally, plays a fundamental role in strong properties, including the SIPP; see [8] for more information. Smooth manifolds $\mathcal{M}$ and $\mathcal{N}$ , both in $\mathbb{R}^{d}$ , intersect transversally at a point ${\bf x}$ if ${\bf x}\in\mathcal{M}\cap\mathcal{N}$ and the intersection of the normal spaces of $\mathcal{M}$ at ${\bf x}$ and of $\mathcal{N}$ at ${\bf x}$ contains only the zero vector. As the next result shows, a matrix $Q\in\mathcal{O}(m,n)$ having the SIPP is equivalent to $\mathcal{Q}(\operatorname{sgn}(Q))$ and $\mathcal{O}(m,n)$ intersecting transversally at $Q$ .

Theorem 3.11.

[6, Theorem 4.5] Let $Q\in\mathcal{O}(m,n)$ have sign pattern $S$ . The manifolds $Q(S)$ and $\mathcal{O}(m,n)$ intersect transversally at $Q$ if and only if $Q$ has the SIPP. If $Q$ has the SIPP, then every superpattern of $S$ allows o-SIPP.

Theorem 3.13 improves the previous result by allowing us to control the relative magnitudes of the formerly zero entries in $Q$ when applying the SIPP. This requires the following theorem of van der Holst, Lovász, and Schrijver.

Theorem 3.12.

[9] Let $\mathcal{M}_{1}(s)$ and $\mathcal{M}_{2}(t)$ be smooth families of manifolds in $\mathbb{R}^{d}$ , and assume that $\mathcal{M}_{1}(0)$ and $\mathcal{M}_{2}(0)$ intersect transverally at ${\bf y}_{0}$ . Then there is a neighborhood $W\subseteq\mathbb{R}^{2}$ of the origin and a continuous function $f:W\to\mathbb{R}^{d}$ such that $f(0,0)={\bf y}_{0}$ and for each $\epsilon=(\epsilon_{1},\epsilon_{2})\in W$ , $\mathcal{M}_{1}(\epsilon_{1})$ and $\mathcal{M}_{2}(\epsilon_{2})$ intersect transversally at $f(\epsilon)$ .

Note that the statement of Theorem 3.12 applies to a more general setting than we require. For our purposes, one of the smooth families of manifolds is replaced with a manifold. In such a setting we may think of $f$ as a continuous function of one variable from an interval about the origin to $\mathbb{R}^{d}$ .

Theorem 3.13.

Let $Q\in\mathcal{O}(m,n)$ have sign pattern $S$ . If $Q$ has the SIPP, then for all $A\in\mathbb{R}^{m\times n}$ with $A\circ Q=O$ , for every $\epsilon$ sufficiently small there is a matrix $M_{\epsilon}\in\mathcal{Q}(S)$ such that $M_{\epsilon}+\epsilon A\in\mathcal{O}(m,n)$ . Moreover, $M_{\epsilon}+\epsilon A$ has the SIPP.

Proof 3.14.

Suppose that $Q=[q_{ij}]$ has the SIPP and let $A=[a_{ij}]\in\mathbb{R}^{m\times n}$ satisfy $A\circ Q=O$ . Define the smooth family of manifolds $\mathcal{M}_{A}(t)$ by

\mathcal{M}_{A}(t)=\{B=[b_{ij}]\in\mathbb{R}^{m\times n}:\operatorname{sgn}(b_{ij})=\operatorname{sgn}(q_{ij})\text{ if }q_{ij}\not=0,\text{ and }b_{ij}=a_{ij}t\text{ if }q_{ij}=0\}

for $t\in(-1,1)$ . Since $Q$ has the SIPP, $\mathcal{O}(m,n)$ and $\mathcal{M}_{A}(0)=\mathcal{Q}(S)$ intersect transversally at $Q$ by Theorem 3.11. By Theorem 3.12, there exists a continuous function $f:(-1,1)\to\mathbb{R}^{m\times n}$ such that $f(0)=Q$ and the manifolds $\mathcal{M}_{A}(\epsilon)$ and $\mathcal{O}(m,n)$ intersect transversally at $f(\epsilon)$ for each $\epsilon>0$ sufficiently small. Since $f$ is continuous we may choose $\epsilon$ small enough so that $M_{\epsilon}:=f(\epsilon)\circ C_{Z}\in\mathcal{Q}(S)$ , where $Z$ is the zero-nonzero pattern of $Q$ and $C_{Z}$ is the unique $(1,0)$ -matrix in $\mathcal{Q}(Z)$ . To complete the proof, observe that $f(\epsilon)=M_{\epsilon}+\epsilon A$ . Moreover, $f(\epsilon)$ has the SIPP by Theorem 3.11 since $\mathcal{M}_{A}(\epsilon)$ and $\mathcal{O}(m,n)$ intersect transversally at $f(\epsilon)$ .

We apply the previous theorem to prove the next result.

Proposition 3.15.

Let

S=\left[\begin{array}[]{c|c}S_{1}&O\\ \hline\cr S_{3}&S_{4}\end{array}\right]

be a sign pattern that allows row orthogonality, and let $S_{4}^{\prime}$ be a submatrix of $S_{4}$ with the same number of rows as $S_{4}$ . If $S_{4}^{\prime}$ allows o-SIPP, then

S^{\prime}=\left[\begin{array}[]{c|c}S_{1}&O\\ \hline\cr S_{3}&S_{4}^{\prime}\end{array}\right]

allows row orthogonality.

Proof 3.16.

Let $Q$ be a row orthogonal realization of $S$ . Then

Q=\left[\begin{array}[]{c|c}Q_{1}&O\\ \hline\cr Q_{3}&Q_{4}\end{array}\right],

where the partition is consistent with that of $S$ . Assume that $S_{4}^{\prime}$ allows o-SIPP. Then there exists a row orthogonal realization $Q_{4}^{\prime}$ of $S_{4}^{\prime}$ with the SIPP. Then $\left[\begin{array}[]{c|c}O&Q_{4}^{\prime}\end{array}\right]$ is row orthogonal and, by Lemma 1.2, has the SIPP. By Theorem 3.13, there exists an $\epsilon>0$ and a matrix $M_{\epsilon}^{\prime}$ such that $\left[\begin{array}[]{c|c}\epsilon Q_{3}&M_{\epsilon}^{\prime}\end{array}\right]$ is row orthogonal and $\operatorname{sgn}(Q_{4}^{\prime})=\operatorname{sgn}(M_{\epsilon}^{\prime})$ . Since $Q$ is row orthogonal, $Q_{1}Q_{3}^{T}=O$ . Therefore,

Q^{\prime}=\left[\begin{array}[]{c|c}Q_{1}&O\\ \hline\cr\epsilon Q_{3}&M_{\epsilon}^{\prime}\end{array}\right]

is row orthogonal and $\operatorname{sgn}(Q^{\prime})=S^{\prime}$ .

3.2 Sign patterns requiring o-SIPP

In this section we present results concerning sign patterns that require o-SIPP. As we shall see, both the number of zero entries and the location of the zero entries in a sign pattern $S$ play an important role in determining whether $S$ requires o-SIPP.

While sign patterns that require o-SIPP have not been previously studied, there are some known results that are closely related to requiring o-SIPP. For example, consider the $n\times n$ lower Hessenberg matrix

H=\left[\begin{array}[]{ccccc}1&-1&0&\cdots&0\\ \vdots&\ddots&-2&\ddots&\vdots\\ \vdots&&\ddots&\ddots&0\\ \vdots&&&\ddots&-(n-1)\\ 1&\cdots&\cdots&\cdots&1\end{array}\right],

which has orthogonal rows. The proof of Corollary 5.2 in [6] implies that any sign pattern that has the same zero-nonzero pattern as $H$ and allows orthogonality requires o-SIPP.

The next lemma provides an example of a structural property that guarantees a matrix has the SIPP and is used to establish Corollary 3.19, which is a slightly more general result than [6, Corollary 5.2]. For any integer $k=1-m,\dots,n-1$ , the $k$ -th diagonal of an $m\times n$ matrix $A=[a_{ij}]$ is the list of entries $a_{ij}$ such that $j-i=k$ . The $k$ -th diagonal terminology is also applied to sign patterns.

Lemma 3.17.

Let $A=[a_{ij}]\in\mathbb{R}^{m\times n}$ be a wide matrix with full rank. Suppose that there is an integer $k$ such that $0\leq k\leq n-1$ , each entry of $A$ on the $r$ -th diagonal is nonzero for $1-m\leq r\leq k$ , and each entry of $A$ on the $r$ -th diagonal is zero for $k<r\leq n-1$ . Then $A$ has the SIPP.

Proof 3.18.

Note that if $k=n-1$ , then $A$ is nowhere zero and hence has the SIPP. Suppose that $k<n-1$ . Let $c=\min\{n-k-1,m\}$ and $A_{\ell}=A[\{1,\ldots,\ell\},\{1\ldots,\ell+k+1\}]$ for $\ell=1,\ldots,c$ . We begin by successively showing that each $A_{\ell}$ has the SIPP. Since $A_{1}$ contains a nonzero entry, Lemma 3.9 implies $A_{1}$ has the SIPP. Suppose that $A_{i}$ has the SIPP for some $i\in\{1,\ldots,c-1\}$ . Then Lemma 3.9 and Lemma 1.2 imply that $A_{i+1}$ has the SIPP. If $c=m$ , then $A=\left[\begin{array}[]{c|c}A_{c}&O\end{array}\right]$ has the SIPP by Lemma 1.2. Otherwise, $A=\left[\begin{array}[]{c}A_{c}\\ \hline\cr B\end{array}\right]$ , where $B$ is nowhere zero. By Lemma 3.9, $A$ has the SIPP.

Corollary 3.19.

Let $S$ be an $m\times n$ wide sign pattern. Suppose that there is an integer $k$ such that $0\leq k\leq n-1$ , each entry of $S$ on the $r$ -th diagonal is nonzero for $1-m\leq r\leq k$ , and each entry of $S$ on the $r$ -th diagonal is zero for $k<r\leq n-1$ . If $S$ allows row orthogonality, then $S$ requires o-SIPP.

For sign equivalent matrices $A$ and $B$ , $A\in\mathcal{O}(m,n)$ implies $B\in\mathcal{O}(m,n)$ and $A$ has the SIPP implies $B$ has the SIPP. Thus the analogous statement with the upper part nonzero is also true.

Corollary 3.20.

Let $S$ be a wide $m\times n$ sign pattern. Suppose that there is an integer $k$ such that $1-m\leq k\leq 0$ , each entry of $S$ on the $r$ -th diagonal is nonzero for $k\leq r\leq n-1$ , and each entry of $S$ on the $r$ -th diagonal is zero for $1-m\leq r<k$ . If $S$ allows row orthogonality, then $S$ requires o-SIPP.

In this paper, a nonzero hollow matrix (respectively, sign pattern) is a square matrix (respectively, sign pattern) with zeros along the main diagonal and nonzero entries everywhere else. Recall that a signature matrix is a diagonal matrix with diagonal entries equal to $\pm 1$ . Matrices $A$ and $B$ are signature equivalent if there exist signature matrices $D_{1}$ and $D_{2}$ such that $D_{1}AD_{2}=B$ . Similarly, sign patterns $S$ and $R$ are signature equivalent if there exist signature matrices $D_{1}$ and $D_{2}$ such that $D_{1}C_{S}D_{2}=C_{R}$ . Theorem 5.7 in [6] states that a nonzero hollow matrix $Q\in\mathcal{O}(n)$ has the SIPP if and only if $Q$ is not signature equivalent to a symmetric hollow matrix. The following corollary is an immediate consequence.

Corollary 3.21.

Let $S$ be a nonzero hollow sign pattern that allows orthogonality. If $S$ is not signature equivalent to a symmetric hollow sign pattern, then $S$ requires o-SIPP. If $S$ is signature equivalent to a symmetric hollow sign pattern, then $S$ does not allow o-SIPP.

As an example, consider

S=\left[\begin{array}[]{cccc}0&+&+&+\\ +&0&-&+\\ +&+&0&-\\ +&-&+&0\end{array}\right].

It is not difficult to verify that $C_{S}$ has orthogonal rows, and hence $S$ allows orthogonality. Further, $S$ is not signature equivalent to a symmetric sign pattern. Thus, $S$ requires o-SIPP.

Let $G$ be a graph with vertex set $V(G)=\{v_{1},\dots,v_{m}\}$ and edge set $E(G)=\{e_{1},\dots,e_{\ell}\}$ . The (vertex-edge) incidence matrix $R_{G}=[r_{ij}]$ of $G$ is the $m\times\ell$ matrix that has $r_{ij}=1$ if $v_{i}\in e_{j}$ and $r_{ij}=0$ otherwise. An orientation $\vec{G}$ of $G$ is the assignment of a direction to each edge. That is, the edge $e_{j}=\{v_{i},v_{k}\}$ is replaced by exactly one of the two arcs $(v_{i},v_{k})$ or $(v_{k},v_{i})$ ; the arc associated with $e_{j}$ is denoted by $\vec{e}_{j}$ . The incidence matrix $R_{\vec{G}}=[r_{ij}]$ of an orientation $\vec{G}$ of $G$ is the $m\times\ell$ matrix that has $r_{ij}=-1$ if $\vec{e}_{j}=(v_{i},v_{k})$ , $r_{ij}=1$ if $\vec{e}_{j}=(v_{k},v_{i})$ , and $r_{ij}=0$ otherwise.

Consider the complete graph $K_{m}$ and an orientation $\vec{K}_{m}$ . For $m\geq 2$ , define the $m\times 2\binom{m}{2}$ matrix $R(K_{m},\vec{K}_{m})=[R_{K_{m}}|R_{\vec{K}_{m}}]$ and its sign pattern $S(K_{m},\vec{K}_{m})=\operatorname{sgn}(R(K_{m},\vec{K}_{m}))$ . The sign pattern $S(K_{m},\vec{K}_{m})$ was shown to have a row orthogonal realization with the SIPP in [5]. We now show that $S(K_{m},\vec{K}_{m})$ requires o-SIPP. We note that this sign pattern will be instrumental in Section 4 for studying random sign patterns that allow row orthogonality.

Theorem 3.22.

For $m\geq 2$ and any orientation $\vec{K}_{m}$ of $K_{m}$ , the sign pattern $S(K_{m},\vec{K}_{m})$ requires o-SIPP.

Proof 3.23.

For brevity, let $S=S(K_{m},\vec{K}_{m})$ . It is not difficult to verify that $C_{S}$ has orthogonal rows and hence $S$ allows row orthogonality. Let $Q\in\mathcal{Q}(S)$ be row orthogonal and suppose $X=[x_{ij}]\in\operatorname{sym}(m)$ satisfies $(XQ)\circ Q=O$ . By Lemma 3.5, $x_{ii}=0$ for $i=1,\dots,m$ . For $i\neq k$ , there is a unique edge $e_{j}=\{v_{i},v_{k}\}$ . Then applying Lemma 3.7 to column $j$ gives that $x_{ik}=0$ . Thus $X=O$ and $Q$ has the SIPP.

Let $Q\in\mathcal{O}(m,n)$ . It is an immediate consequence of Theorem 1.1 that if $Q$ has a pair of combinatorially orthogonal rows, then $Q$ does not have the SIPP. Similarly, if $m=n$ and $Q$ has a pair of combinatorially orthogonal columns, then $Q$ does not have the SIPP. Thus, when studying sign patterns that require o-SIPP, it is natural to assume that the rows (and in the square case the columns) are not cominbatorially orthogonal. Note that it is possible for a wide sign pattern to have combinatorially orthogonal columns and still require o-SIPP. For example, consider

S=\left[\begin{array}[]{cccc}+&0&+&+\\ 0&+&+&-\\ 0&-&+&-\end{array}\right]\quad\text{and}\quad A=\left[\begin{array}[]{cccc}1&0&1&1\\ 0&1&1&-1\\ 0&-2&1&-1\end{array}\right].

Observe that $A$ has orthogonal rows. As we shall see, Corollary 3.27 implies $S$ requires o-SIPP.

The remainder of this section investigates how restricting the location and number of zero entries affects whether or not a sign pattern requires o-SIPP. Let $A\in\mathbb{R}^{m\times n}$ be a wide matrix. It is not difficult to verify that if $A$ is nowhere zero, then $A$ has the SIPP. Thus every nowhere zero sign pattern that allows row orthogonality requires o-SIPP. For each additional $0$ entry in $A$ , the equation $(XA)\circ A=O$ imposes one fewer linear equation on the entries of $X$ . This suggests that the more $0$ entries $A$ has, the larger the solution space to $(XA)\circ A=O$ is going to be, reducing the likelihood that $A$ has the SIPP. In fact, this is the intuition behind the next theorem, which bounds the number of zero entries a matrix with the SIPP can have.

Theorem 3.24.

[6] Let $Q\in\mathcal{O}(m,n)$ have the SIPP. Then the number of zero entries in $Q$ is at most $nm-\frac{1}{2}m(m+1)$ .

The location of $0$ entries in a sign pattern $S$ also play an important role in determining if $S$ requires o-SIPP.

Theorem 3.25.

Let $Q=[q_{ij}]\in\mathcal{O}(m,n)$ . Suppose that the zero entries of $Q$ are contained in at most three rows of $Q$ and that no pair of rows is combinatorially orthogonal. Then, $Q$ has the SIPP.

Proof 3.26.

Begin by assuming that the zero entries of $Q$ are contained in at most 1 row. Without loss of generality, the zero entries of $Q$ are contained in the first row and the $(1,1)$ -entry of $Q$ is nonzero. By Lemma 3.9, $Q$ has the SIPP.

Now assume that exactly $k$ rows of $Q$ contain a zero, where $k\in\{2,3\}$ . Without loss of generality, the first $k$ rows each contain a zero. Let $X\in\operatorname{sym}(m)$ and suppose $(XQ)\circ Q=O$ . By Lemma 3.3, $X=Y\oplus O$ , where $Y\in\operatorname{sym}(k)$ . Observe that $(Y\hat{Q})\circ\hat{Q}=O$ , where $\hat{Q}$ is the submatrix of $Q$ formed from the first $k$ rows. Also, note that Lemma 3.5 implies $Y\circ I=O$ .

First, consider the case $k=2$ . Since the rows of $\hat{Q}$ are not combinatorially orthogonal, $\hat{Q}$ has a nowhere zero column. Since $(Y\hat{Q})\circ\hat{Q}=O$ , Lemma 3.7 implies that the off-diagonal entries of $Y$ are zero. This, together with $Y\circ I=O$ , implies $Y=O$ .

Now consider the case $k=3$ . Suppose first that an off-diagonal entry of $Y$ , without loss of generality the $(1,2)$ -entry, is zero, so $Y=\left[\begin{array}[]{ccc}0&0&y_{1}\\ 0&0&y_{2}\\ y_{1}&y_{2}&0\\ \end{array}\right].$ Since the rows of $\hat{Q}$ are not combinatorially orthogonal, $\hat{Q}$ has a column with nonzero entries in the first and third rows. Then $(Y\hat{Q})\circ\hat{Q}=O$ implies $y_{1}=0$ ; similarly $y_{2}=0$ . So suppose that $Y$ is a nonzero hollow matrix. Then by Lemma 3.7, and the preceding argument, no column of $\hat{Q}$ has exactly one zero entry. This, along with the fact that no pair of rows of $\hat{Q}$ are combinatorially orthogonal, implies $\hat{Q}$ has a nowhere zero column ${\bf q}_{j}$ . Observe that $(Y\hat{Q})\circ\hat{Q}=O$ implies $Y{\bf q}_{j}={\bf 0}$ . This is impossible since $\operatorname{rank}(Y)=3$ . Thus, $Y=O$ and $Q$ has the SIPP.

Corollary 3.27.

Suppose $S$ is an $m\times n$ sign pattern that allows row orthogonality such that the zero entries of $S$ are contained in at most three rows of $S$ and that no pair of rows are combinatorially orthogonal. Then, $S$ requires o-SIPP.

As the next example illustrates, Corollary 3.27 cannot be extended to 4 or more rows.

Example 3.28.

\thlabel

ex:n-zero_n-rowDefine the $n\times(n+1)$ matrix

A=\left[\begin{array}[]{cc|cccc|cc}0&\sqrt{n-2}&3-n&1&\cdots&1&\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\ 0&\sqrt{n-2}&1&3-n&\cdots&1&\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\ \vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots&\vdots\\ 0&\sqrt{n-2}&1&1&\cdots&3-n&\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\ \hline\cr 0&\sqrt{n-2}&1&1&\cdots&1&\frac{3-n}{\sqrt{2}}&\frac{3-n}{\sqrt{2}}\\ \hline\cr\sqrt{n-2}&0&1&1&\cdots&1&\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\ -\sqrt{n-2}&0&1&1&\cdots&1&\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\end{array}\right].

Observe that the rows of $A$ are orthogonal. It can be verified that

X=\begin{bmatrix}0&\cdots&0&1&-1\\ \vdots&\ddots&\vdots&\vdots&\vdots\\ 0&\cdots&0&1&-1\\ 1&\cdots&1&0&0\\ -1&\cdots&-1&0&0\end{bmatrix}\in\mathbb{R}^{n\times n}

satisfies $(XA)\circ A=O$ . Since $X=X^{T}$ and $\operatorname{rank}A=n$ , it follows that $A$ does not have the SIPP.

Even if we also prohibit combinatorially orthogonal columns, there are examples of sign patterns with the zero entries restricted to the first four rows that do not require o-SIPP, as seen in the next example, which utilizes a construction method in [5].

Example 3.29.

Consider

Q=\left[\begin{array}[]{ccccccc}-9&9&0&0&3\sqrt{2}&-6\sqrt{2}&6\sqrt{2}\\ 9&-9&0&0&3\sqrt{2}&-6\sqrt{2}&6\sqrt{2}\\ 0&0&-9&9&-6\sqrt{2}&3\sqrt{2}&6\sqrt{2}\\ 0&0&9&-9&-6\sqrt{2}&3\sqrt{2}&6\sqrt{2}\\ 3\sqrt{2}&3\sqrt{2}&-6\sqrt{2}&-6\sqrt{2}&8&8&4\\ -6\sqrt{2}&-6\sqrt{2}&3\sqrt{2}&3\sqrt{2}&8&8&4\\ 6\sqrt{2}&6\sqrt{2}&6\sqrt{2}&6\sqrt{2}&4&4&2\\ \end{array}\right]\quad\text{and}\quad X=\left[\begin{array}[]{cccc}0&0&1&-1\\ 0&0&1&-1\\ 1&-1&0&0\\ 1&-1&0&0\\ \end{array}\right]\oplus O.

It is readily verified that the rows of $Q$ are orthogonal and $(XQ)\circ Q=O$ . Thus, $\operatorname{sgn}(Q)$ allows orthogonality but does not require o-SIPP.

By restricting the number of zero entries, we obtain the following result.

Proposition 3.30.

Let $Q\in\mathcal{O}(m,n)$ have at most four zero entries. Suppose that no pair of rows and no pair of columns columns of $Q$ are combinatorially orthogonal. Then $Q$ has the SIPP.

Proof 3.31.

Observe that if the zero entries of $Q=[q_{ij}]$ are contained in at most three rows, then Theorem 3.25 implies $Q$ has the SIPP. So, suppose that each zero entry of $Q$ is contained in a unique row.

Assume first that $m=n=4$ . If $Q$ has a nowhere zero column, then Proposition 1.5 and Theorem 3.25 imply $Q$ has the SIPP. Otherwise, without loss of generality, $Q$ is a nonzero hollow matrix. Theorem 3.2 in [2] guarantees that $Q$ is not symmetric. Thus, Corollary 3.21 implies $Q$ has the SIPP.

Now assume that $n\geq 5$ (and $m\geq 4$ ). Without loss of generality, $Q$ has the form

Q=\left[\begin{array}[]{c|c}Q_{1}&Q_{2}\\ \hline\cr Q_{3}&Q_{4}\end{array}\right],

where all four zero entries of $Q$ are contained in $Q_{1}$ such that each column and each row of $Q_{1}$ contains a zero entry. Note that $Q_{1}$ has four rows, $Q_{2}$ is nowhere zero, and $Q_{3}$ and $Q_{4}$ may be vacuous. We proceed via cases.

We first resolve the case where $Q_{1}$ has exactly one column, i.e., $Q_{1}={\bf 0}$ . Then $Q_{2}\in\mathcal{O}(4,n-1)$ is nowhere zero. Thus $Q_{2}$ has the SIPP and, by Lemma 3.9, $Q$ has the SIPP.

Suppose that $Q_{1}$ has at least two columns. Let $X\in\operatorname{sym}(m)$ and suppose $(XQ)\circ Q=O$ . By Lemma 3.3, $X=Y\oplus O$ , where $Y$ is symmetric and has four rows. Further, Lemma 3.5 implies $Y\circ I=O$ , i.e., $Y$ has the form

Y=\left[\begin{array}[]{cccc}0&y_{1}&y_{2}&y_{3}\\ y_{1}&0&y_{4}&y_{5}\\ y_{2}&y_{4}&0&y_{6}\\ y_{3}&y_{5}&y_{6}&0\end{array}\right].

We now consider the case where $Q_{1}$ has a column ${\bf c}$ with exactly one zero entry. Without loss of generality, the zero appears in the last entry of ${\bf c}$ . Then $(Y{\bf c})\circ{\bf c}={\bf 0}$ implies $y_{1}=y_{2}=y_{4}=0$ . It now follows from $(YQ_{2})\circ Q_{2}=O$ that $y_{3}=y_{5}=y_{6}=0$ . Thus, $Y=O$ and $Q$ has the SIPP.

For the final case, assume that $Q_{1}$ has exactly two columns that contain exactly two zero entries each. Since the first two columns cannot be combinatorialy orthogonal, there must be at least five rows. Then, without loss of generality,

\hat{Q}:=Q[\{1,\ldots,5\},\{1,\ldots,n\}]=\left[\begin{array}[]{cc|c}0&q_{12}&{\bf v}_{1}^{T}\\ 0&q_{22}&{\bf v}_{2}^{T}\\ q_{31}&0&{\bf v}_{3}^{T}\\ q_{41}&0&{\bf v}_{4}^{T}\\ \hline\cr q_{51}&q_{52}&{\bf w}^{T}\end{array}\right].

From $(YQ_{1})\circ Q_{1}=O$ it follows that $y_{1}=y_{6}=0$ . If $y_{i}=0$ for $i\in\{2,3,4,5\}$ , then $(YQ_{2})\circ Q_{2}=O$ implies $Y=O$ . Suppose this is not the case, i.e., $y_{i}\not=0$ for all $i\in\{2,3,4,5\}$ . Then $(YQ_{2})\circ Q_{2}=O$ implies $y_{2}{\bf v}_{1}^{T}+y_{4}{\bf v}_{2}^{T}={\bf 0}^{T}$ , and thus ${\bf v}_{2}=a{\bf v}_{1}$ for some nonzero value $a$ . Since $Q$ is row orthogonal

$\displaystyle 0$	$\displaystyle=$	$\displaystyle q_{12}q_{22}+{\bf v}_{1}^{T}{\bf v}_{2}=q_{12}q_{22}+a(1-q_{12}^{2}),$
$\displaystyle 0$	$\displaystyle=$	$\displaystyle q_{22}q_{52}+{\bf v}_{2}^{T}{\bf w}=q_{22}q_{52}+a{\bf v}_{1}^{T}{\bf w},\text{ and}$
$\displaystyle 0$	$\displaystyle=$	$\displaystyle q_{12}q_{52}+{\bf v}_{1}^{T}{\bf w}.$

From the last two equations $a=q_{22}/q_{12}$ . Substituting this into the first equation implies $q_{22}=0$ , a contradiction. Thus, $Y=O$ and $Q$ has the SIPP.

It is possible to show that if $Q\in\mathcal{O}(m,n)$ has at most five zero entries, no pair of rows and no pair of columns columns of $Q$ are combinatorially orthogonal, then $Q$ has the SIPP. However, with the available tools, the argument is not illuminating and does not warrant the space that would be required. As the next example illustrates, it is possible for a sign pattern with six zero entries to allow row orthogonality, not have combinatorially orthogonal rows or columns, and not require o-SIPP.

Example 3.32.

Consider the sign pattern

S=\left[\begin{array}[]{cccccc}0&+&+&+&+&+\\ +&0&+&-&+&-\\ +&+&0&+&-&-\\ +&-&+&0&-&+\\ +&+&-&-&0&+\\ +&-&-&+&+&0\end{array}\right].

Observe that $C_{S}$ is a conference matrix, i.e., $C_{S}$ is hollow, every off-diagonal entry is $1$ or $-1$ , and $C_{S}^{T}C_{S}=(n-1)I$ . Hence $S$ allows orthogonality. By Corollary 3.21, $S$ does not require o-SIPP. In fact, it is not difficult to see that $C_{S}$ does not have the SIPP since the symmetric matrix $X=C_{S}$ satisfies $(XC_{S})\circ C_{S}=O$ .

3.3 Nowhere zero sign patterns that minimally allow orthogonality

In this section we determine the nowhere zero sign patterns with at most five rows that minimally allow orthogonality. These and previously known results are summarized in Table 3.1 at the end of this section, which lists a representative of each equivalence class of $m\times n$ nowhere zero sign patterns that minimally allow orthogonality for $m\leq 5$ . Recall that a sign pattern $S$ minimally allows orthogonality provided $S$ allows row orthogonality and every sign pattern obtained from $S$ by deleting one or more columns does not allow row orthogonality.

A complete characterization of nowhere zero sign patterns with at most 4 rows that minimally allow orthogonality was presented in [5]. We summarize these results in the following theorem.

Theorem 3.33.

[5, Section 5.2] Let $S$ be an $m\times n$ nowhere zero sign pattern. If $m\leq 3$ , then $S$ minimally allows orthogonality if and only if $n=3$ and $S$ is row and column PPO. If $m=4$ , then $S$ minimally allows orthogonality if and only if $n=4$ and $S$ is row and column PPO, or $S$ is sign equivalent to

\left[\begin{array}[]{ccccc}-&-&+&+&+\\ +&+&-&-&+\\ +&+&+&+&-\\ +&+&+&+&+\end{array}\right].

We now determine all $5\times n$ nowhere zero sign patterns that minimally allow orthogonality. The next theorem establishes the square case.

Theorem 3.34.

[5, Theorem 7.9] Let $S$ be a $5\times 5$ nowhere zero sign pattern. Then $S$ allows orthogonality if and only if $S$ is row and column PPO.

Lemma 3.35.

Let $S$ be a $5\times 4$ nowhere zero sign pattern. Then $S$ is sign equivalent to a sign pattern with at most 5 negative entries.

Proof 3.36.

By scaling the rows and columns of $S$ we can obtain the sign patterns

S_{1}=\left[\begin{array}[]{c|ccc}+&+&+&+\\ \hline\cr+&\\ +&&\hbox{\multirowsetup$R$}\\ +&\\ +&\\ \end{array}\right]\quad\text{and}\quad S_{2}=\left[\begin{array}[]{c|ccc}-&+&+&+\\ \hline\cr+&\\ +&&\hbox{\multirowsetup$-R$}\\ +&\\ +&\\ \end{array}\right].

If $R$ contains at most 5 negative entries, then the proof is complete. So, suppose that $R$ has at least 6 negative entries.

First consider the case where $R$ has exactly 6 negative entries. If a row (or column) of $R$ has 3 negatives, then negating the corresponding row (or column) of $S_{1}$ reduces the total number of negative entries to at most 5. Otherwise $R$ has two rows ${\bf r}_{1}$ and ${\bf r}_{2}$ , each containing exactly 2 negative entries, and a third row that contains a negative entry; let $j$ denote the column index of this entry. Observe that negating the rows of $S_{1}$ corresponding to ${\bf r}_{1}$ and ${\bf r}_{2}$ does not change the total number of negative entries. Thus, we can scale the rows of $S_{1}$ so that column $j$ has 3 negative entries. Negating column $j$ now reduces the total number of negatives to at most 5.

Now suppose that $R$ has at least 7 negative entries. Then $S_{2}$ has at most 6 negative entries. As before, we can reduce the total number of negative entries to at most 5 if a row (or column) of $-R$ contains at least 3 negative entries, or if $-R$ has two rows that each contain exactly 2 negative entries. Thus, we may assume $-R$ has 1 row with exactly 2 negative entries and 2 columns with exactly 2 negative entries. Without loss of generality $S_{2}$ is of the form

\left[\begin{array}[]{c|ccc}-&+&+&+\\ \hline\cr+&-&-&+\\ +&+&+&-\\ +&+&-&+\\ +&-&+&+\end{array}\right]\quad\text{or}\quad\left[\begin{array}[]{c|ccc}-&+&+&+\\ \hline\cr+&-&-&+\\ +&+&+&-\\ +&+&+&-\\ +&+&-&+\end{array}\right].

Negate columns 2 and 3, and rows 1 and 3 in the first case. Negate row 2 and column 4 in the second case.

The next example uses the ideas illustrated in Example 2.9.

Example 3.37.

We can apply Theorem 2.7 to the matrices

A_{1}={\small\left[\begin{array}[]{cccccc}-424&-297&42&382&424&212\\ 290&48&-578&-70&247&392\\ 126&32&2&536&-490&310\\ 466&4&39&404&305&-407\\ 49&579&384&12&255&301\end{array}\right]}\text{ and }A_{2}={\small\left[\begin{array}[]{cccccc}-246&-246&369&123&369&123\\ 494&-254&7&127&7&314\\ 174&230&-11&-421&396&75\\ 284&107&414&56&-41&-392\\ 2&477&51&367&69&231\end{array}\right]}

to obtain row orthogonal matrices with the same sign patterns: For $A_{1}$ , the value $\delta=\frac{1}{268}>.003$ is obtained from row $3$ of $A_{1}$ and the value $\epsilon={400\over 409890583973\sqrt{409890583973}}<0.0007$ is obtained from rows $1$ and $2$ . Thus $\epsilon<\frac{1}{5-1}$ . Since $r_{5}$ is increasing on its domain, $r_{5}(\epsilon)<r_{5}(0.0007)<0.003<\delta$ . For $A_{2}$ , the value $\delta=\frac{2}{477}>.004$ is obtained from row $5$ of $A_{2}$ and the value $\epsilon={1\over 395150\sqrt{118545}}<0.0009$ is obtained from rows $1$ and $2$ . Thus $\epsilon<\frac{1}{5-1}$ and $r_{5}(\epsilon)<r_{5}(0.0009)<0.004<\delta$ .

Theorem 3.38.

Let $S$ be a $5\times n$ nowhere zero sign pattern. Then $S$ minimally allows orthogonality if and only if $n=5$ and $S$ is row and column PPO, or $S$ is sign equivalent to

S_{1}={\small\left[\begin{array}[]{cccccc}-&-&+&+&+&+\\ +&+&-&-&+&+\\ +&+&+&+&-&+\\ +&+&+&+&+&-\\ +&+&+&+&+&+\end{array}\right]},\ S_{2}={\small\left[\begin{array}[]{cccccc}-&-&-&+&+&+\\ +&+&-&+&+&+\\ +&+&+&-&-&+\\ +&+&+&+&+&-\\ +&+&+&+&+&+\end{array}\right]},\ \text{or}\ S_{3}={\small\left[\begin{array}[]{cccccc}-&-&+&+&+&+\\ +&-&+&+&+&+\\ +&+&-&-&+&+\\ +&+&+&+&-&-\\ +&+&+&+&+&+\end{array}\right]}.

Proof 3.39.

Observe that each of the three patterns $S_{1},S_{2}$ , and $S_{3}$ allows row orthogonality by Examples 2.9 and 3.37. Removing a column from one of $S_{1},S_{2}$ or $S_{3}$ results in a $5\times 5$ sign pattern with a duplicate column, and such a sign pattern is not column PPO. So by Theorem 3.34, removing a column from one of $S_{1},S_{2}$ and $S_{3}$ results in a sign pattern that does not allow orthogonality. Thus, each of $S_{1},S_{2}$ and $S_{3}$ minimally allows row orthogonality.

Assume that $S$ minimally allows orthogonality. Without loss of generality the first row and first column of $S$ have all positive entries. Suppose that $S$ has $d$ distinct columns ${\bf c}_{1},\ldots,{\bf c}_{d}$ . It is easy to see that $d\geq 4$ : If $S$ had at most 3 distinct columns, then $S$ would have at most $4$ distinct rows, contradicting the fact that $S$ is row PPO.

First consider the case where $S$ has $d=5$ distinct columns. Since $S$ is row PPO,

R=\left[\begin{array}[]{c|c|c|c|c}{\bf c}_{1}&{\bf c}_{2}&{\bf c}_{3}&{\bf c}_{4}&{\bf c}_{5}\\ \end{array}\right]

is row PPO. Observe that $R$ is column PPO since ${\bf c}_{1},\ldots,{\bf c}_{5}$ are distinct. By Theorem 3.34, $R$ allows orthogonality. Since $S$ minimally allows orthogonality, $S=R$ .

Now suppose that $d>5$ and let

R=\left[\begin{array}[]{c|c|c|c|c}{\bf c}_{1}&{\bf c}_{2}&{\bf c}_{3}&{\bf c}_{4}&{\bf c}_{5}\\ \end{array}\right].

As before, if $R$ is row PPO, then $R$ allows orthogonality. Since $S$ minimally allows orthogonality, it follows from the preceding argument that $R$ is not row PPO. Without loss of generality

R=\left[\begin{array}[]{r|rrrr}+&+&+&+&+\\ +&+&+&+&+\\ \hline\cr+&\\ +&&\lx@intercol\hfil\hat{R}\hfil\lx@intercol\\ +&\\ \end{array}\right],

where the columns of $\hat{R}$ are distinct and belong to the set

\left\{\left[\begin{array}[]{ccc}+\\ +\\ -\end{array}\right],\left[\begin{array}[]{ccc}+\\ -\\ +\end{array}\right],\left[\begin{array}[]{ccc}-\\ +\\ +\end{array}\right],\left[\begin{array}[]{ccc}+\\ -\\ -\end{array}\right],\left[\begin{array}[]{ccc}-\\ +\\ -\end{array}\right],\left[\begin{array}[]{ccc}-\\ -\\ +\end{array}\right],\left[\begin{array}[]{ccc}-\\ -\\ -\end{array}\right]\right\}.

Either $\hat{R}$ contains a column with exactly one negative entry or every column of $\hat{R}$ has at least two negative entries. Observe that in the latter case, negating the last three rows of $R$ results in a column with all positive entries and a column with exactly one negative entry. Thus, we may assume

R=\left[\begin{array}[]{cc|ccc}+&+&+&+&+\\ +&+&+&+&+\\ \hline\cr+&+&+&-&*\\ +&+&-&*&*\\ +&-&*&*&*\end{array}\right].

Since $S$ allows row orthogonality, ${\bf c}_{j}=(+,-,*,*,*)^{T}$ for some $j\geq 6$ . Observe that

\left[\begin{array}[]{c|c|c|c|c}{\bf c}_{1}&{\bf c}_{2}&{\bf c}_{3}&{\bf c}_{4}&{\bf c}_{j}\\ \end{array}\right]

is row and column PPO and hence allows orthogonality by Theorem 3.34. This is a contradiction since $S$ minimally allows orthogonality. Thus, $d\leq 5$ .

Finally, we consider the case where $S$ has exactly $d=4$ distinct columns. Let $R=\left[\begin{array}[]{c|c|c|c}{\bf c}_{1}&{\bf c}_{2}&{\bf c}_{3}&{\bf c}_{4}\end{array}\right]$ . By Lemma 3.35 we may assume that $R$ has at most $5$ negative entries. Observe that at least $4$ rows of $R$ contain a negative entry since $S$ is row PPO.

Suppose $R$ has exactly $4$ negative entries. Then $R$ is sign equivalent to

\left[\begin{array}[]{cccc}-&+&+&+\\ +&-&+&+\\ +&+&-&+\\ +&+&+&-\\ +&+&+&+\end{array}\right]

and we assume $R$ has this form. Observe that $S$ can be obtained from $R$ by duplicating some of the columns. By Theorem 1.6 we must duplicate at least 2 distinct columns of $R$ to obtain $S$ . It follows that, up to sign equivalence, $S$ contains the submatrix

S_{1}=\left[\begin{array}[]{cccccc}-&-&+&+&+&+\\ +&+&-&-&+&+\\ +&+&+&+&-&+\\ +&+&+&+&+&-\\ +&+&+&+&+&+\end{array}\right].

Suppose that $R$ has $5$ negatives. Observe that $R$ cannot have exactly 1 negative per row, as this would contradict $S$ being row PPO. Further, at most 1 row of $R$ has 2 negatives, otherwise we have 2 positive rows, which violates row PPO. By these considerations, $R$ is sign equivalent to

\left[\begin{array}[]{cccc}-&-&+&+\\ +&-&+&+\\ +&+&-&+\\ +&+&+&-\\ +&+&+&+\\ \end{array}\right]

and we assume $R$ has this form. As before, $S$ can be obtained from $R$ by duplicating at least 2 distinct columns of $R$ . Observe that duplicating only columns 1 and 2 of $R$ violates Theorem 1.6. Duplicating columns 1 and 3 is sign equivalent to duplicating columns 1 and 4. Duplicating columns 2 and 3 is sign equivalent to duplicating columns 2 and 4. Thus, up to sign equivalence, $S$ contains one of

S_{2}=\left[\begin{array}[]{cccccc}-&-&-&+&+&+\\ +&+&-&+&+&+\\ +&+&+&-&-&+\\ +&+&+&+&+&-\\ +&+&+&+&+&+\end{array}\right],\quad S_{3}=\left[\begin{array}[]{cccccc}-&-&+&+&+&+\\ +&-&+&+&+&+\\ +&+&-&-&+&+\\ +&+&+&+&-&-\\ +&+&+&+&+&+\end{array}\right]

S_{4}=\left[\begin{array}[]{cccccc}-&-&-&+&+&+\\ +&-&-&+&+&+\\ +&+&+&-&-&+\\ +&+&+&+&+&-\\ +&+&+&+&+&+\end{array}\right]

as a submatrix. Observe that $S_{4}$ is sign equivalent to $S_{2}$ (negate rows $1,2$ and $5$ , and negate columns $4,5$ and $6$ ; then appropriately permute rows and columns). By Examples 2.9 and 3.37, $S_{1},S_{2}$ and $S_{3}$ allow row orthogonality. Since $S$ minimally allows orthogonality, $S$ is sign equivalent to $S_{1},S_{2},$ or $S_{3}$ .

Remark 3.40.

Characterizing all $6\times n$ sign patterns that minimally allow orthogonality may require a new approach. However, in doing so, we may learn a great deal about sign patterns that allow row orthogonality. Consider the $6\times 8$ sign pattern

S=\left[\begin{array}[]{cccccccc}+&+&+&+&+&+&+&+\\ +&+&+&-&-&-&+&+\\ +&+&+&+&+&+&-&+\\ +&+&+&-&-&-&-&-\\ +&+&+&+&+&+&+&-\\ +&+&+&-&-&-&+&-\end{array}\right].

Deleting any number of columns will contradict Theorem 1.6, so if $S$ allows row orthogonality, then it minimally allows orthogonality. Using the techniques described in Example 2.9, we were unable to find a row orthogonal realization of $S$ . It would be very interesting if this sign pattern does not allow row orthogonality. It is not too difficult to verify that $S$ satisfies the conditions of Theorem 1.6, so this would unveil a new necessary condition for sign patterns to allow row orthogonality.

Rows	Unique sign patterns (up to sign equivalence)
1	$\left[\begin{array}[]{c}+\end{array}\right]$
2	$\left[\begin{array}[]{cc}+&-\\ +&+\end{array}\right]$
3	$\left[\begin{array}[]{ccc}+&-&+\\ +&+&-\\ +&+&+\end{array}\right]$
4	$\left[\begin{array}[]{cccc}+&-&+&+\\ +&+&-&+\\ +&+&+&-\\ +&+&+&+\end{array}\right]$ , $\left[\begin{array}[]{cccc}+&-&-&+\\ +&+&-&+\\ +&+&+&-\\ +&+&+&+\end{array}\right]$ , $\left[\begin{array}[]{cccc}-&+&+&+\\ +&-&+&+\\ +&+&-&+\\ +&+&+&-\end{array}\right]$ , $\left[\begin{array}[]{ccccc}-&+&+&+&+\\ +&-&+&-&+\\ +&+&-&+&-\\ +&+&+&+&+\end{array}\right]$
	$\left[\begin{array}[]{rrrrr}+&-&-&+&+\\ +&+&-&-&+\\ +&+&+&-&-\\ +&+&+&+&-\\ +&+&+&+&+\end{array}\right]$ , $\left[\begin{array}[]{rrrrr}-&-&+&+&+\\ +&-&-&+&+\\ +&+&-&-&+\\ +&+&+&+&-\\ +&+&+&+&+\end{array}\right]$ , $\left[\begin{array}[]{rrrrr}-&-&+&+&+\\ +&-&-&+&+\\ +&+&-&+&+\\ +&+&+&-&+\\ +&+&+&+&-\end{array}\right]$ ,
5	$\left[\begin{array}[]{rrrrr}-&-&+&+&+\\ +&-&-&+&+\\ +&+&+&-&-\\ +&+&+&+&-\\ +&+&+&+&+\end{array}\right]$ , $\left[\begin{array}[]{rrrrr}-&-&+&+&+\\ +&-&-&+&+\\ +&+&+&-&+\\ +&+&+&+&-\\ +&+&+&+&+\end{array}\right]$ , $\left[\begin{array}[]{rrrrr}+&-&-&+&+\\ +&+&-&+&+\\ +&+&+&-&-\\ +&+&+&+&-\\ +&+&+&+&+\end{array}\right]$ ,
	$\left[\begin{array}[]{rrrrr}-&-&+&+&+\\ +&-&+&+&+\\ +&+&-&+&+\\ +&+&+&-&+\\ +&+&+&+&-\end{array}\right]$ , $\left[\begin{array}[]{rrrrr}-&+&+&+&+\\ +&-&+&+&+\\ +&+&-&+&+\\ +&+&+&-&+\\ +&+&+&+&-\end{array}\right]$ , $\left[\begin{array}[]{rrrrr}+&-&+&+&+\\ +&+&-&+&+\\ +&+&+&-&+\\ +&+&+&+&-\\ +&+&+&+&+\end{array}\right]$ ,
	$\left[\begin{array}[]{cccccc}-&-&+&+&+&+\\ +&+&-&-&+&+\\ +&+&+&+&-&+\\ +&+&+&+&+&-\\ +&+&+&+&+&+\end{array}\right]$ , $\left[\begin{array}[]{cccccc}-&-&-&+&+&+\\ +&+&-&+&+&+\\ +&+&+&-&-&+\\ +&+&+&+&+&-\\ +&+&+&+&+&+\end{array}\right]$ , $\left[\begin{array}[]{cccccc}-&-&+&+&+&+\\ +&-&+&+&+&+\\ +&+&-&-&+&+\\ +&+&+&+&-&-\\ +&+&+&+&+&+\end{array}\right]$

Table 3.1: One representative of each sign-equivalence class of

m\times n

nowhere zero sign patterns that minimally allow orthogonality for

m\leq 5

4 Likelihood a random sign pattern allows row orthogonality

The question of finding the probability that $m$ vectors sampled from $\{\pm 1\}^{n}$ are linearly independent has attracted recent attention in the literature. This problem can equivalently be stated as asking for the probability that a random matrix in $\{\pm 1\}^{m\times n}$ has rank $m$ (the literature is most interested in the case when $m=n$ ). In particular, Tikhomirov [12] answered this question in a strong form by showing that this probability is bounded below by $1-\bigl{(}{1\over 2}+o(1)\bigr{)}^{m}$ whenever $n\geq m$ ; in particular, when $n\geq m$ the probability tends toward $1$ as $m$ tends toward $\infty$ .

In this section, we consider the adjacent problem of determining the threshold $t(m)$ such that a random matrix in $\{+,-\}^{m\times n}$ with $n\geq t(m)$ allows row orthogonality with probability tending toward $1$ as $m$ tends toward $\infty$ .

Let $f(n)$ and $g(n)$ be functions from the non-negative integers to the reals. Then $f(n)=o(g(n))$ if $\lim_{n\to\infty}{f(n)}/{g(n)}=0$ , and $f(n)=\omega(g(n))$ if $g(n)=o(f(n))$ . An event $E=E(n)$ happens with high probability as $n\to\infty$ if $\Pr[E]=1-o(1)$ . The union bound is the fact that the probability that at least one of a set of the events happens is at most the sum of the probabilities of the events.

For a probability distribution $\mu$ on a set $\Omega$ , we write $x\sim\mu$ to mean that $x$ is distributed according to $\mu$ . If $\Omega$ is a finite set, then we write $x\sim\Omega$ to mean that $x$ is chosen uniformly from $\Omega$ . We write $x_{1},\dots,x_{n}\sim\mu$ to indicate that $x_{1},\dots,x_{n}$ are distributed according to $\mu$ and are mutually independent from one another. For a positive integer $n$ , $\mu^{n}$ denotes the product distribution on $\Omega^{n}$ where each entry is drawn independently from $\mu$ . Similarly, for positive integers $m$ and $n$ , $\mu^{m\times n}$ denotes the product distribution on $\Omega^{m\times n}$ where each entry is drawn independently from $\mu$ . For an index set $\alpha$ , let $\Omega^{\alpha}$ denote the set of vectors with entries in $\Omega$ indexed by $\alpha$ . We write $\mu^{\alpha}$ to mean the product distribution on $\Omega^{\alpha}$ where each entry is drawn independently from $\mu$ .

We will need two forms of the Chernoff bound, which we state here.

Theorem 4.1.

[1, Corollary A.1.2] Let $X_{i}$ , $1\leq i\leq n$ , be mutually independent random variables with $\Pr[X_{i}=1]=\Pr[X_{i}=-1]=\frac{1}{2}$ and $X=X_{1}+\cdots+X_{n}.$ Let $a>0$ . Then

\Pr[|X|>a]<2e^{-a^{2}/2n}.

Theorem 4.2.

[11, Remark 9.2] Suppose $X_{1},\ldots,X_{n}$ are independent random variables taking values from the set $\{0,1\}$ . Let $X=X_{1}+\ldots+X_{n}$ . Then for any $\delta\geq 0$

\Pr[X\leq(1-\delta)\mathbb{E}[X]]\leq\exp(-\delta^{2}\mathbb{E}[X]/2).

For a fixed $0\leq p\leq 1/2$ , let $\mu_{p}$ denote the distribution on $\{0,\pm 1\}$ where $\mu_{p}(1)=\mu_{p}(-1)=p$ and $\mu_{p}(0)=1-2p$ . The main result of this section, Theorem 4.12, implies that for any fixed $0<p\leq 1/2$ , there is a constant $C=C(p)$ such that if $A\sim{\mu_{p}}^{m\times n}$ where $n\geq m^{2}+Cm\log m$ , then $\operatorname{sgn}(A)$ allows row orthogonality with high probability as $m\to\infty$ . Before proving Theorem 4.12, we use Theorem 2.7 to obtain a slightly weaker result for nowhere zero sign patterns. We include this result since the proof is relatively short and highlights a substantially different approach from Theorem 4.12.

Theorem 4.3.

If $A\sim\{\pm 1\}^{m\times n}$ with $n\geq 17m^{2}\log m$ , then $\operatorname{sgn}(A)$ allows row orthogonality with high probability as $m\to\infty$ .

Proof 4.4.

Let ${\bf x}_{i}$ denote the $i$ th row of $A$ , so ${\bf x}_{1},\dots,{\bf x}_{m}\sim\{\pm 1\}^{n}$ . Observe that $\lVert{\bf x}_{i}\rVert_{2}=\sqrt{n}$ and that $\delta({\bf x}_{i})=1$ for each $i\in[m]$ . Set

\epsilon=\sqrt{{\frac{17}{4}\log m\over n}},

and observe that $0\leq\epsilon\leq{1\over 2m}$ since $n\geq 17m^{2}\log m$ and so

r_{m}(\epsilon)=\sqrt{{1+\epsilon\over(1-(m-2)\epsilon)(1-(m-1)\epsilon)}}-1\leq\sqrt{{1+{1\over 2m}\over\bigl{(}1-{m-2\over 2m}\bigr{)}\bigl{(}1-{m-1\over 2m}\bigr{)}}}-1=2\sqrt{{m(m+1/2)\over(m+2)(m+1)}}-1<1.

Thus, if $\lvert\langle{\bf x}_{i},{\bf x}_{j}\rangle\rvert\leq\epsilon n$ for all $i\neq j\in[m]$ , then we may apply Theorem 2.7 to locate a set of orthogonal vectors $\widetilde{{\bf x}}_{1},\dots,\widetilde{{\bf x}}_{m}$ such that $\operatorname{sgn}(\widetilde{{\bf x}}_{i})=\operatorname{sgn}({\bf x}_{i})$ . Thus, in order to conclude the proof, it suffices to show that $\lvert\langle{\bf x}_{i},{\bf x}_{j}\rangle\rvert\leq\epsilon n$ for all $i\neq j\in[m]$ with high probability as $m\to\infty$ .

Since ${\bf x}_{1},\dots,{\bf x}_{m}\sim\{\pm 1\}^{n}$ are independent, we may apply the Chernoff bound in Theorem 4.1 to bound

\Pr\bigl{[}\lvert\langle{\bf x}_{i},{\bf x}_{j}\rangle\rvert>\epsilon n\bigr{]}<2e^{-\epsilon^{2}n/2}

for any $i\neq j\in\{1,\dots,m\}$ . By the union bound,

	$\displaystyle\Pr\bigl{[}\lvert\langle{\bf x}_{i},{\bf x}_{j}\rangle\rvert\leq\epsilon n,\ \forall i\neq j\in[m]\bigr{]}$	$\displaystyle\geq 1-\sum_{i<j\in[m]}\Pr\bigl{[}\lvert\langle{\bf x}_{i},{\bf x}_{j}\rangle\rvert>\epsilon n\bigr{]}\geq 1-\binom{m}{2}2e^{-\epsilon^{2}n/2}$
		$\displaystyle\geq 1-m^{2}e^{-\epsilon^{2}n/2}=1-m^{-1/8}=1-o(1).$

We now show how to improve Theorem 4.3 by using the SIPP. Recall that Theorem 3.22 states that the sign pattern $S(K_{m},\vec{K}_{m})$ requires o-SIPP. We say that a pair of negative $4$ -cycles are column-disjoint if the column indices of the negative $4$ -cycles are all distinct. Observe that any sign pattern that has a collection of column-disjoint negative $4$ -cycles between every pair of rows is sign equivalent to a superpattern of $\left[\begin{array}[]{c|c}S(K_{m},\vec{K}_{m})&O\end{array}\right]$ . So by Theorem 1.1 and Theorem 1.3, we have the following observation.

Observation 4.5.

Let $S$ be an $m\times n$ sign pattern. If $S$ has a collection of column-disjoint negative 4-cycles between every pair of rows, then $S$ allows row orthogonality.

In the following proofs, we must condition on the outcome of a stochastic process. For those readers unfamiliar with these ideas, we recommend consulting [13, Chapter 9].

Lemma 4.6.

Fix any $0<p\leq 1/2$ . If ${\bf x}_{1},\dots,{\bf x}_{m}\sim\mu_{p}^{n}$ , then the probability that we can find distinct integers $i_{1},j_{1},i_{2},j_{2},\dots,i_{m},j_{m}\in[n]$ such that $({\bf x}_{k})_{i_{k}}=1$ and $({\bf x}_{k})_{j_{k}}=-1$ for all $k\in[m]$ is at least

1-{1\over p}(1-p)^{n-2m+1}

Proof 4.7.

We employ the following greedy algorithm to find the required set $W_{m}=\{i_{1},j_{1},\dots,i_{m},j_{m}\}$ of indices:

Initialize $U_{0}=[n]$ and $W_{0}=\emptyset$ . At time $t=1,\dots,m$ , do the following:

1.

Reveal ${\bf x}_{t}$ .
2.

Attempt to locate some $i_{t},j_{t}\in U_{t-1}$ for which $({\bf x}_{t})_{i_{t}}=1$ and $({\bf x}_{t})_{j_{t}}=-1$ . If such $i_{t},j_{t}$ are found, then set $U_{t}=U_{t-1}\setminus\{i_{t},j_{t}\}$ and $W_{t}=W_{t-1}\cup\{i_{t},j_{t}\}$ . If no such $i_{t},j_{t}$ exist, then exit with failure.

If the above algorithm succeeds, then we have located the desired $W_{m}$ .

Let $\tau$ be the round on which the algorithm fails, setting $\tau=m+1$ if the algorithm succeeds. In order to complete the proof, we show that

\Pr[\tau\leq m]\leq{1\over p}(1-p)^{n-2m+1}.

Fix any $t\in[m]$ and consider conditioning on the event $\{\tau\geq t\}$ . Since $\tau\geq t$ if and only if the algorithm has succeeded locating the set $U_{t-1}$ , we may condition on such an outcome. Now, conditioned on the algorithm locating $U_{t-1}$ , we observe that $\tau=t$ if and only if ${\bf x}_{t}[U_{t-1}]$ is nonnegative or nonpositive. Furthermore, before the $t$ th loop, no information is known about the vector ${\bf x}_{t}$ and so ${\bf x}_{t}[U_{t-1}]\sim\mu_{p}{}^{U_{t-1}}$ . We may therefore bound

\Pr[\tau=t\ |\ U_{t-1}]=\Pr\bigl{[}{\bf x}_{t}[U_{t-1}]\in\{0,1\}^{U_{t-1}}\cup\{0,-1\}^{U_{t-1}}\ \bigm{|}\ U_{t-1}\bigr{]}\leq 2(1-p)^{\lvert U_{t-1}\rvert}=2(1-p)^{n-2(t-1)}.

Since this bound is independent of $U_{t-1}$ , we may bound

\Pr[\tau=t]\leq\Pr[\tau=t\ |\ \tau\geq t]\leq 2(1-p)^{n-2(t-1)}.

We therefore conclude that

	$\displaystyle\Pr[\tau\leq m]$	$\displaystyle=$	$\displaystyle\sum_{t=1}^{m}\Pr[\tau=m]\leq\sum_{t=1}^{m}2(1-p)^{n-2(t-1)}=2\sum_{k=0}^{m-1}(1-p)^{n-2m+2+2k}$
		$\displaystyle=$	$\displaystyle 2{(1-p)^{n-2m+2}-(1-p)^{n+2}\over(2-p)p}\leq{2\over(2-p)p}(1-p)^{n-2m+2}\leq{1\over p}(1-p)^{n-2m+1},$

where the final inequality follows from the fact that ${1-p\over 2-p}\leq{1\over 2}$ .

We now use the above lemma to locate collections of column-disjoint negative $4$ -cycles.

Lemma 4.8.

Fix any ${\bf x}\in\{\pm 1\}^{n}$ and any $0<p\leq 1/2$ . Assume $A\sim\mu_{p}^{m\times n}$ and set $B=\left[\begin{array}[]{c}{\bf x}^{T}\\ \hline\cr A\end{array}\right].$ Then $\operatorname{sgn}(B)$ contains column-disjoint negative $4$ -cycles between its first row and all other rows with probability at least

1-{1\over p}(1-p)^{n-2m+1}.

Proof 4.9.

Let $D$ be the diagonal matrix whose $i$ th diagonal entry is the $i$ th entry of ${\bf x}$ . Observe that $\operatorname{sgn}(B)$ is sign equivalent to $\operatorname{sgn}(BD)=\operatorname{sgn}\left(\left[\begin{array}[]{ccc}1&\cdots&1\\ \hline\cr&AD&\end{array}\right]\right)$ . Since $\mu_{p}(1)=\mu_{p}(-1)$ and ${\bf x}\in\{\pm 1\}^{n}$ , $AD\sim\mu_{p}^{m\times n}$ . Thus $\operatorname{sgn}(B)$ contains column-disjoint negative $4$ -cycles between its first row and all other rows if and only if we can locate distinct $i_{1},\dots,i_{m},j_{1},\dots,j_{m}\in[n]$ so that $({\bf w}_{k})_{i_{k}}=1$ and $({\bf w}_{k})_{j_{k}}=-1$ . As such, the conclusion follows from Lemma 4.6.

Lemma 4.10.

Fix a number $0<p\leq 1/2$ . Assume $A\sim\mu_{p}^{m\times n}$ , where $n\geq m^{2}+mr+{2m\over p}$ for some $r\in\{0,\dots,m\}$ . Then the probability that $\operatorname{sgn}(A)$ contains a collection of column-disjoint negative $4$ -cycles between every pair of rows is bounded below by

1-me^{-m/8}-{m\over p}(1-p)^{r}.

Proof 4.11.

In order to locate a collection of negative $4$ -cycles between every pair of rows of $\operatorname{sgn}(A)$ , we employ the following greedy algorithm:

Suppose that the rows of $A$ are ${\bf x}_{1},\dots,{\bf x}_{m}$ . Initialize $U_{0}=[n]$ . At time $t=1,\dots,m-1$ do the following:

1.

Reveal ${\bf x}_{t}[U_{t-1}]$ .
2.

Find some $W_{t}\subseteq\operatorname*{supp}({\bf x}_{i}[U_{t-1}])$ with $\lvert W_{t}\rvert=2(m-t)+r$ and set $U_{t}=U_{t-1}\setminus W_{t}$ . If no such $W_{t}$ exists, then fail.
3.

Reveal $A[\{t+1,\dots,m\},W_{t}]$
4.

Locate column-disjoint negative $4$ -cycles in $\operatorname{sgn}(A)$ between row $t$ and all rows $k>t$ , all of whose columns reside within $W_{t}$ . If such negative $4$ -cycles cannot be found, then fail.

If the above algorithm succeeds, then $\operatorname{sgn}(A)$ contains a collection of column-disjoint negative $4$ -cycles between every pair of rows.

Let $\tau$ denote the first round on which the algorithm fails, setting $\tau=m$ if the algorithm succeeds. In order to prove the claim, we argue that

\Pr[\tau\leq m-1]\leq me^{-m/8}+{m\over p}(1-p)^{r}.

Fix any $t\in[m-1]$ . Let $\mathcal{S}_{t}$ denote the event that the algorithm fails at step 2 on the $t$ th loop, and let $\mathcal{F}_{t}$ denote the event that the algorithm fails at step 4 on the $t$ th loop. Certainly $\{\tau=t\}=\mathcal{S}_{t}\cup\mathcal{F}_{t}$ . We begin by bounding the probability of $\mathcal{S}_{t}$ .

Consider conditioning on the event $\{\tau\geq t\}$ . Of course, if $\tau\geq t$ , then the algorithm has succeeded in locating the set $U_{t-1}$ . Furthermore, conditioned on $\{\tau\geq t\}$ and $U_{t-1}$ , observe that prior to the $t$ th loop of the algorithm, no entries within $A[\{t,\dots,m\},U_{t-1}]$ have been revealed; therefore $A[\{t,\dots,m\},U_{t-1}]\sim\mu_{p}^{\{t,\dots,m\}\times U_{t-1}}$ . In particular, ${\bf x}_{t}[U_{t-1}]\sim\mu_{p}^{U_{t-1}}$ . Now, $W_{t}$ cannot be located if and only if $\lvert\operatorname*{supp}({\bf x}_{t}[U_{t-1}])\rvert<2(m-t)+r$ . Additionally,

	$\displaystyle\lvert U_{t-1}\rvert$	$\displaystyle=$	$\displaystyle n-\sum_{j=1}^{t-1}\bigl{(}2(m-j)+r\bigr{)}\geq m^{2}+rm+{2m\over p}-\sum_{j=1}^{t-1}\bigl{(}2(m-j)+r\bigr{)}$
		$\displaystyle=$	$\displaystyle{2m\over p}+m^{2}+rm-(t-1)(2m-t)-(t-1)r\geq{2m\over p}.$

We can therefore fix a subset $U\subseteq U_{t-1}$ with $\lvert U\rvert={\left\lfloor{2m\over p}\right\rfloor}$ . From the earlier observation, we know that ${\bf x}_{t}[U]\sim\mu_{p}^{U}$ and so we may bound

$\displaystyle\Pr[\mathcal{S}_{t}\ \|\ \{\tau\geq t\},U_{t-1}]$	$\displaystyle=$	$\displaystyle\Pr\bigl{[}\lvert\operatorname*{supp}({\bf x}_{t}[U_{t-1}])\rvert<2(m-t)+r\ \bigm{\|}\ \{\tau\geq t\},U_{t-1}\bigr{]}$
	$\displaystyle\leq$	$\displaystyle\Pr\bigl{[}\lvert\operatorname*{supp}({\bf x}_{t}[U])\rvert<2(m-t)+r\ \bigm{\|}\ \{\tau\geq t\},U_{t-1}\bigr{]}$
	$\displaystyle=$	$\displaystyle\Pr_{{\bf x}\sim\mu_{p}^{\lfloor 2m/p\rfloor}}\bigl{[}\lvert\operatorname*{supp}{\bf x}\rvert<2(m-t)+r\bigr{]}$
	$\displaystyle\leq$	$\displaystyle\Pr_{{\bf x}\sim\mu_{p}^{\lfloor 2m/p\rfloor}}\bigl{[}\lvert\operatorname*{supp}{\bf x}\rvert<3m-1\bigr{]},$

where the final inequality follows from the fact that $t\geq 1$ and $r\leq m$ .

Next, we note that if ${\bf x}\sim\mu_{p}^{\lfloor 2m/p\rfloor}$ , then ${\mathbb{E}[\lvert\operatorname*{supp}{\bf x}\rvert]}=2p\left\lfloor{2m\over p}\right\rfloor\geq 4m-2p\geq 4m-1$ and so

$\displaystyle\Pr_{{\bf x}\sim\mu_{p}^{\left\lfloor 2m/p\right\rfloor}}\bigl{[}\lvert\operatorname*{supp}{\bf x}\rvert<3m-1\bigr{]}$	$\displaystyle\leq$	$\displaystyle\Pr_{{\bf x}\sim\mu_{p}^{\left\lfloor 2m/p\right\rfloor}}\bigl{[}\lvert\operatorname{supp}{\bf x}\rvert<{\mathbb{E}[\lvert\operatorname{supp}{\bf x}\rvert]}-m\bigr{]}$
	$\displaystyle=$	$\displaystyle\Pr_{{\bf x}\sim\mu_{p}^{\left\lfloor 2m/p\right\rfloor}}\left[\lvert\operatorname{supp}{\bf x}\rvert<\left(1-\frac{m}{\mathbb{E}[\lvert\operatorname{supp}{\bf x}\rvert]}\right)\mathbb{E}[\lvert\operatorname*{supp}{\bf x}\rvert]\right]$
	$\displaystyle\leq$	$\displaystyle\exp\biggl{(}-\frac{m^{2}}{2\mathbb{E}[\|\operatorname*{supp}{\bf x}\|]}\biggr{)}=\exp\biggl{(}-{m^{2}\over 4p\left\lfloor{2m\over p}\right\rfloor}\biggr{)}\leq{e^{-m/8}},$

where the second inequality follows from the Chernoff bound in Theorem 4.2. Since this bound is independent of $U_{t-1}$ , we have argued that

(4.4)

\Pr[\mathcal{S}_{t}\ |\ \tau\geq t]\leq e^{-m/8}.

Next, we bound the probability of $\mathcal{F}_{t}$ . In order for $\mathcal{F}_{t}$ to hold, it must be the case that $\tau\geq t$ and that $\mathcal{S}_{t}$ does not hold; in particular, the algorithm must have succeeded in locating the set $W_{t}$ . By construction, just after locating $W_{t}$ , no entries within $A[\{t+1,\dots,m\},W_{t}]$ have been revealed; therefore $A[\{t+1,\dots,m\},W_{t}]\sim\mu_{p}^{\{t+1,\dots,m\}\times W_{t}}$ . Since $\Pr[\mathcal{F}_{t}\ |\ W_{t}]$ is equal to the probability of not finding a collection of column disjoint negative 4-cycles between the first row of $A[\{t+1,\dots,m\},W_{t}]$ and the remaining rows, we may appeal to Lemma 4.8 to bound

\Pr[\mathcal{F}_{t}\ |\ W_{t}]\leq{1\over p}(1-p)^{\lvert W_{t}\rvert-2(m-t)+1}\leq{1\over p}(1-p)^{r}.

Since this bound is independent of $W_{t}$ , we have shown that

(4.5)

\Pr[\mathcal{F}_{t}\ |\ \{\tau\geq t\},\overline{\mathcal{S}_{t}}]\leq{1\over p}(1-p)^{r},

where $\overline{\mathcal{S}_{t}}$ denotes the event that $\mathcal{S}_{t}$ does not occur.

Combining (4.4) and (4.5) we have shown that

	$\displaystyle\Pr[\tau=t]$	$\displaystyle\leq$	$\displaystyle\Pr[\tau=t\ \|\ \tau\geq t]=\Pr[\mathcal{S}_{t}\ \|\ \tau\geq t]+\Pr[\mathcal{F}_{t}\ \|\ \tau\geq t]$
		$\displaystyle\leq$	$\displaystyle\Pr[\mathcal{S}_{t}\ \|\ \tau\geq t]+\Pr[\mathcal{F}_{t}\ \|\ \{\tau\geq t\},\overline{\mathcal{S}_{t}}]\leq e^{-m/8}+{1\over p}(1-p)^{r},$

where the first equality holds since $\mathcal{S}_{t}$ and $\mathcal{F}_{t}$ partition $\{\tau=t\}$ .

Using this inequality, we finally bound

\Pr[\tau\leq m-1]=\sum_{t=1}^{m-1}\Pr[\tau=t]\leq\sum_{t=1}^{m-1}\left(e^{-m/8}+{1\over p}(1-p)^{r}\right)\leq me^{-m/8}+{m\over p}(1-p)^{r},\vspace{-5pt}

as needed.

Theorem 4.12.

For any fixed $0<p\leq 1/2$ , if $A\sim\mu_{p}^{m\times n}$ and

n\geq m^{2}+m\log_{1/(1-p)}m+\omega(m),

then $\operatorname{sgn}(A)$ allows row orthogonality with high probability as $m\to\infty$ .

Proof 4.13.

Suppose that

n\geq m^{2}+m\log_{1/(1-p)}m+f(m),

where $f(m)=\omega(m)$ . Without loss of generality, we may additionally suppose that $f(m)=o(m^{2})$ . Set $r=\log_{1/(1-p)}m+\frac{f(m)}{m}-{2\over p}$ which is certainly bounded above by $m$ for all sufficiently large $m$ since $f(m)=o(m^{2})$ . Furthermore, by decreasing $f(m)$ by some amount no more than $m$ , we may ensure that $r$ is an integer, the lower bound on $n$ remains true, $f(m)=\omega(m)$ , and $f(m)=o(m^{2})$ . Now, since $f(m)=\omega(m)$ and $0<p\leq 1/2$ is fixed, we have that

n\geq m^{2}+m\log_{1/(1-p)}m+f(m)\geq m^{2}+mr+{2m\over p}

for all sufficiently large $m$ . Thus, we may apply Lemma 4.10 to learn that $\operatorname{sgn}(A)$ contains a collection of column-disjoint negative $4$ -cycles between every pair of rows (and hence has a row orthogonal realization) with probability at least

1-me^{-m/8}-{m\over p}(1-p)^{r}=1-me^{-m/8}-{m\over p}(1-p)^{-\log_{(1-p)}m}(1-p)^{{f(m)\over m}-{2\over p}}=1-me^{-m/8}-{1\over p}(1-p)^{{f(m)\over m}-{2\over p}},

which tends to $1$ as $m\to\infty$ since $f(m)=\omega(m)$ and $0<p\leq 1/2$ .

We suspect that Theorem 4.12 is not best possible.

Question 4.14.

Determine the threshold $t(m)$ such that if $S\sim\{+,-\}^{m\times n}$ with $n\geq t(m)$ , then $S$ has a row orthogonal realization with high probability as $m\to\infty$ .

Theorem 4.12 implies that $t(m)\leq m^{2}+m\log_{2}m+\omega(m)$ . Observe that $t(m)\geq m$ and it is possible that this is the correct answer. As shown in the next theorem, the best known obstruction (see Theorem 1.6) does not block $t(m)=m$ .

Theorem 4.15.

Let $X\sim\{\pm 1\}^{m\times m}$ . Then with high probability as ${m}\to\infty$ the matrix $X$ does not contain an $r\times s$ submatrix $Y$ such that $r+s={m}+2$ and $\operatorname{rank}Y=1$ .

Proof 4.16.

Let $\Omega$ denote the set of pairs $({\bf x},{\bf y})$ , where ${\bf x}\in\{\pm 1\}^{r}$ , ${\bf y}\in\{\pm 1\}^{s}$ and the first entry of ${\bf x}$ is $1$ . Observe that the map $({\bf x},{\bf y})\mapsto{\bf x}{\bf y}^{T}$ is a bijection between $\Omega$ and the set of rank 1 matrices in $\{\pm 1\}^{r\times s}$ . Thus the probability that $Y\sim\{\pm 1\}^{r\times s}$ has rank 1 is precisely $2^{-(r-1)(s-1)}$ .

The number of $r\times s$ submatrices of $X$ is $\binom{m}{r}\binom{m}{s}$ . By the union bound, the probability that $X$ contains an $r\times s$ submatrix $Y$ such that $r+s={m}+2$ and $\operatorname{rank}Y=1$ is at most

\sum_{r=2}^{m}\binom{m}{r}\binom{m}{m+2-r}2^{-(r-1)(m+1-r)}=\sum_{k=1}^{m-1}\binom{m}{k+1}\binom{m}{m+1-k}2^{-k(m-k)}.

We show that this sum tends toward $0$ as $m\to\infty$ by showing that

\binom{m}{k+1}\binom{m}{m+1-k}<\frac{2^{k(m-k)}}{m^{2}}

for all $1\leq k\leq m-1$ , provided $m$ is sufficiently large. If $k\leq 2$ or $k\geq m-2$ , then for $m$ sufficiently large

\binom{m}{k+1}\binom{m}{m+1-k}\leq m^{4}<\frac{2^{k(m-k)}}{m^{2}}.

For $3\leq k\leq m-3$ , we have

\binom{m}{k+1}\binom{m}{m+1-k}\leq 2^{2m}<\frac{2^{3(m-3)}}{m^{2}}\leq\frac{2^{k(m-k)}}{m^{2}}.

Acknowledgements

The research of Z. Brennan, C. Cox, B. Curtis, E. Gomez-Leos, and C. Thompson was partially supported by NSF grant 1839918 and the authors thank the National Science Foundation.

References

[1] N. Alon and J.H. Spencer. The probabilistic method. John Wiley & Sons, 2016.
[2] R.F. Bailey and R. Craigen. On orthogonal matrices with zero diagonal. Electron. J. Linear Algebra, 35:307–318, 2019.
[3] J. Bourgain, V.H. Vu and P.M. Wood. On the singularity probability of discrete random matrices, J.Functional Analysis 258 (2010), no. 2, 559–603. MR2557947
[4] H. Cohn, A. Kumar and G. Minton. Optimal simplices and codes in projective spaces. Geometry & Topology, 20:1289–1357, 2016.
[5] B.A. Curtis. Sign Patterns of Row Orthogonal Matrices. PhD thesis, 2020.
[6] B.A. Curtis and B.L. Shader. Sign patterns of orthogonal matrices and the strong inner product property. Linear Algebra and its Applications, 592: 228–259, 2020.
[7] M. Fiedler, “Problem 12,” in Proceedings: Theory of Graphs and Its Application. Prague: Publishing House of the Czechoslovakia Academy of Sciences, 1964, p. 160.
[8] L. Hogben, J.C.-H. Lin, B.L. Shader. Inverse Problems and Zero Forcing for Graphs. American Mathematical Society (Mathematical Surveys and Monographs, 260), Providence, RI, 2022.
[9] H. van der Holst, L. Lovász, and A. Schrijver. The Colin de Verdière graph parameter. In Graph Theory and Combinatorial Biology (L. Lovász, A. Gyárfás, G. Katona, A. Recski, and L. Székely, editors), János Bolyai Mathematical Society, Budapest, 1999, pp. 29–85.
[10] C.R. Johnson and C. Waters. Sign patterns occurring in orthogonal matrices. Linear and Multilinear Algebra, 44: 287–299, 1998.
[11] H. Tijms. Probability: A lively introduction. Cambridge University Press, 2018.
[12] K. Tikhomirov. Singularity of random Bernoulli matrices. Ann. of Math. (2) 191 (2) 593 - 634, 2018.
[13] D. Williams. Probability with martingales. Cambridge University Press, 1991.