Finite affine indefinite trichotomy for indecomposable gcms

The graph joining $i,j$ when $a_{ij}<0$ is connected: its connected components give a forbidden block partition otherwise, and a block partition disconnects it. If $x\ge 0$ and $Ax\ge 0$, then at a zero coordinate $i$, $(Ax{)}_i={\sum }_{j\mathrm{\ne }i}{a}_{ij}{x}_j\le 0$. Equality forces every neighbor to have zero coordinate. Propagating along finite paths proves $x=0$ or $x>0$.

Suppose $K_A$ contains a nonzero nonnegative vector $u$, so $u>0$ by step 1.1. If $K_A$ is not contained in $\{0\}\cup \{x>0\}$, take $v\in K_A$ with some negative coordinate (a nonnegative exception is excluded by step 1.1). Along the segment from $v$ to $u$ there is a point $z=tu+(1-t)v\ge 0$ with at least one zero coordinate and $0<t<1$. Step 1.1 gives $z=0$, whence $v$ is a negative multiple of $u$ and $0=tAu+(1-t)Av$ forces $Au=Av=0$. For any $w\in K_A$, if $w$ has a negative coordinate repeat with $u,w$; if $w>0$ repeat with $w,v$. In either case $w\in \mathbb{R}u$. Thus $K_A=\ker A=\mathbb{R}u$. Otherwise $K_A\subset \{0\}\cup \{x>0\}$; then a nonzero kernel vector would put both it and its negative in this cone, impossible. So $A$ is invertible, and $A^{-1}\mathbf{1}\in K_A\setminus \{0\}$ is strictly positive with image $\mathbf{1}>0$. These are precisely the affine and finite clauses.

If $A$ has either clause of step 2.1, no $v>0$ can have $Av<0$: otherwise $-v\in K_A$ has negative coordinates and a nonzero image, contradicting either description of $K_A$. Contraposition of F3 with $C=A$ gives a nonzero $u\ge 0$ with $A^{t}u\ge 0$. Apply step 2.1 to $A^t$. Its rank equals that of $A$ by Gaussian elimination, so its clause is finite when $A$ is invertible and affine when $A$ has corank one. Repeating with the transpose proves both transpose implications. If $K_A\cap \{x\ge 0\}=\{0\}$, the transpose has the same property: otherwise step 2.1 and the just-proved transpose implication contradict it. F3 with $C=A$ now supplies $v>0$, $Av<0$. This gives the indefinite clause and its transpose invariance.

The three clauses are disjoint by their cone and rank conditions and exhaustive by steps 2.1–3.1. A positive vector with strictly positive image excludes affine and indefinite by their cone conditions. A positive null vector excludes finite by invertibility and indefinite by its cone condition. A positive vector with negative image puts its negative in $K_A$ with strictly positive image, excluding both finite and affine. Thus the three positive-vector conditions are each sufficient as well as necessary. The affine null ray and corank follow from step 2.1.

For later use, every connected proper principal submatrix of an affine $A$ is finite type: restrict a positive null vector $u$ to a connected index subset $J$. Then $A_J{u}_J=-A_{J,J^c}{u}_{J^c}\ge 0$ and is nonzero, since connectivity of the full graph gives an edge across the partition. Step 4.1 excludes indefinite type for $A_J$, and its affine cone condition excludes a nonzero nonnegative image, so it is finite. For finite $A$, restricting a positive vector with positive image gives $A_J{u}_J>0$, since the omitted off-diagonal contribution is nonpositive. Hence each connected principal submatrix is finite in that case too.

Assume $A$ is finite or affine. If its graph has a cycle, take a shortest simple cycle of length $k\ge 3$. It has no chord. Its principal matrix $C$ has diagonal 2 and paired edges $-r_i,-s_i$ around the cycle with positive integers $r_i,s_i$. It is finite or affine by step 5.1, or by the assumption if it is the whole graph. Choose $w>0$ with $Cw\ge 0$ by step 4.1. In $M=\mathrm{diag}(w_i^{-1})C\mathrm{diag}(w_i)$ each row sum is nonnegative. Its paired edge magnitudes $r_i^{\mathrm{\prime }},s_i^{\mathrm{\prime }}$ have product $r_i{s}_i\ge 1$. Since $(\sqrt{r_i^{\mathrm{\prime }}}-\sqrt{s_i^{\mathrm{\prime }}}{)}^2\ge 0$, their sum is at least 2. Summing all row sums gives $0\le 2k-{\sum }_i(r_i^{\mathrm{\prime }}+s_i^{\mathrm{\prime }})\le 0$. Equality forces every $r_i{s}_i=1$, hence $r_i=s_i=1$. This cycle matrix has null vector $\mathbf{1}>0$, so is affine by step 4.1; step 5.1 forbids it being a proper principal submatrix. Thus $A=C$ is symmetric.

If the connected graph has no simple cycle, it is a tree: two different simple paths would produce a simple cycle. Fix its least vertex with $d=1$ and propagate $d_j=d_i{a}_{ij}\mathrm{/}{a}_{ji}>0$ along its unique paths. Every edge then satisfies $d_i{a}_{ij}=d_j{a}_{ji}$; nonedges have both sides zero, and diagonal equalities are automatic. Thus $DA$ is symmetric by F2. Together with step 6.1 this proves finite/affine symmetrizability, including the singleton tree.

For any symmetric $B=DA$ and any $u>0$, expansion gives $x^{t}DAx={\sum }_i{d}_i(Au{)}_i{x}_i^2\mathrm{/}{u}_i+{\sum }_{i<j}(-d_i{a}_{ij})u_i{u}_j(x_i\mathrm{/}{u}_i-x_j\mathrm{/}{u}_j{)}^2$. Indeed the second sum has cross coefficient $2d_i{a}_{ij}{x}_i{x}_j$ and diagonal coefficient ${\sum }_{j\mathrm{\ne }i}(-d_i{a}_{ij})u_j\mathrm{/}{u}_i$; adding the first sum leaves diagonal $2d_i$. In finite type choose $Au>0$, so the first sum is strictly positive for $x\mathrm{\ne }0$. In affine type choose $Au=0$; the second sum is nonnegative and vanishes exactly when all ratios $x_i\mathrm{/}{u}_i$ agree along edges, hence everywhere by connectivity. Its kernel is exactly $\mathbb{R}u$. In indefinite type a positive $u$ with $Au<0$ gives $u^{t}DAu<0$, whereas every coordinate vector has value $2d_i>0$. The mutually exclusive quadratic behaviors and the already-exhaustive trichotomy prove all reverse implications as well.