Nonnegative vectors on which a symmetric Z-matrix is nonpositive

A real square matrix is a Z-matrix when its off-diagonal entries are nonpositive. The generalized Cartan matrix 2I - A of a (multi)graph with adjacency matrix A is the basic example. This file proves that a symmetric Z-matrix M whose quadratic form is not positive definite has a nonzero vector δ with nonnegative entries and M δ ≤ 0 entrywise.

For M = 2I - A the condition M δ ≤ 0 reads 2 δᵢ ≤ ∑ⱼ Aᵢⱼ δⱼ at every vertex. A positive definite M admits no such δ, since δᵀ M δ ≤ 0, so for a symmetric Z-matrix the existence of δ is equivalent to the failure of positive definiteness. Such a vector is the input to growth arguments for algebras attached to a graph whose form 2I - A is not positive definite.

More elementarily, over any linearly ordered commutative ring the positive and negative parts of a vector x = x⁺ - x⁻ pair nonpositively under a Z-matrix A: (x⁺)ᵀ A x⁻ ≤ 0.

Main results

• Matrix.posPart_dotProduct_mulVec_negPart_nonpos: with nonpositive off-diagonal entries, the positive and negative parts of a vector pair nonpositively.
• Matrix.exists_nonneg_mulVec_nonpos_of_dotProduct_mulVec_nonpos: a symmetric real Z-matrix with a nonzero vector x satisfying xᵀ M x ≤ 0 has a nonzero nonnegative δ with M δ ≤ 0.
• Matrix.exists_nonneg_mulVec_nonpos_of_not_posDef: the same for a symmetric real Z-matrix that is not positive definite.

References

• V. G. Kac, Infinite dimensional Lie algebras, 3rd ed., Chapter 4, Theorem 4.3, where the finite, affine and indefinite types of a generalized Cartan matrix are separated by the signs of M δ for nonnegative vectors δ.

theorem Matrix.posPart_dotProduct_mulVec_negPart_nonpos {n : Type u_1} [Fintype n] {R : Type u_2} [CommRing R] [LinearOrder R] [IsOrderedRing R] {A : Matrix n n R} (hoff : ∀ (i j : n), i ≠ j → A i j ≤ 0) (x : n → R) : x⁺ ⬝ᵥ A.mulVec x⁻ ≤ 0

The positive and negative parts of a vector pair nonpositively when every off-diagonal entry of the matrix is nonpositive: the diagonal terms vanish because the two parts have disjoint supports.

theorem Matrix.exists_nonneg_mulVec_nonpos_of_dotProduct_mulVec_nonpos {n : Type u_1} [Fintype n] {M : Matrix n n ℝ} (hM : M.IsSymm) (hM0 : ∀ (i j : n), i ≠ j → M i j ≤ 0) {x : n → ℝ} (hx : x ≠ 0) (hxM : x ⬝ᵥ M.mulVec x ≤ 0) : ∃ (δ : n → ℝ), 0 ≤ δ ∧ δ ≠ 0 ∧ M.mulVec δ ≤ 0

A symmetric Z-matrix with a nonpositive value of its form is nonpositive on a nonnegative vector. Let M be a symmetric real matrix with nonpositive off-diagonal entries, and suppose that xᵀ M x ≤ 0 for some nonzero x. Then some nonzero vector δ with nonnegative entries satisfies M δ ≤ 0 entrywise.

theorem Matrix.exists_nonneg_mulVec_nonpos_of_not_posDef {n : Type u_1} [Fintype n] {M : Matrix n n ℝ} (hM : M.IsSymm) (hM0 : ∀ (i j : n), i ≠ j → M i j ≤ 0) (h : ¬M.PosDef) : ∃ (δ : n → ℝ), 0 ≤ δ ∧ δ ≠ 0 ∧ M.mulVec δ ≤ 0

A symmetric Z-matrix that is not positive definite is nonpositive on a nonnegative vector. If a symmetric real matrix M with nonpositive off-diagonal entries is not positive definite, then some nonzero vector δ with nonnegative entries satisfies M δ ≤ 0 entrywise.