The Triangle Inequality and Its Converse

A slightly different, but clearly equivalent statement is the following: if a ≥ b ≥ c ≥ 0 are the lengths of the 3 sides of a triangle, then a ≤ b + c. We will use this alternative formulation as it is easier to state and prove the converse and its generalization.

Converse of the triangle inequality on the plane

The converse of the triangle inequality on the plane is also true: If a ≥ b ≥ c ≥ 0 and a ≤ b + c then there exists a triangle whose sides have lengths a, b and c respectively. Equivalently this can be restated as: If a ≥ b ≥ c ≥ 0 and a ≤ b + c, then there exists complex numbers A, B and C with |A|=a, |B| = b, |C| = c such that A+B+C = 0.

The following is a simple construction of such a triangle. First we show that d = (b²+c² - a²)/(2bc) satisfies |d| ≤ 1.This follows from the fact that d = ((b+c)² -a²-2bc)/(2bc) = -1 + ((b+c)² - a²)/(2bc) ≥ -1. and d= ((b-c)² -a²+2bc)/(2bc) = ((b-c)² -a²)/(2bc) + 1 ≤ 1.

Thus we can choose 0 ≤ ϕ = cos⁻¹(d) ≤ π which satisfies a² = b²+c²-2bc cos(ϕ) and the law of cosines shows that the triangle with sides of length b and c and angle ϕ will have a third side of length a. (see Fig. 1).

The converse of the generalized triangle inequality is true on the plane as well. If r₁ ≥ rᵢ and r₁ ≤ ∑ᵢ>₁ rᵢ , then there is an n-sided polygon with rᵢ as the lengths of its sides (Fig. 2). Setting one vertex of the polygon at the origin of the complex plane this can be reformulated as:

Lemma 1 [Camion and Hoffman, 1966]

Let n ≥ 2 and r₁ ≥ r₂ ≥ ... ≥ rₙ ≥ 0 be real numbers such that r₁ ≤ ∑ᵢ>₁ rᵢ, then there exists complex numbers cᵢ such that |cᵢ| = rᵢ and c₁ + c₂ + ... + cₙ = 0.

Proof: As stated in [Camion and Hoffman, 1966] this is easily proved by induction. For n=2 this implies that |r₁| = |r₂| and thus we can set c₁ = r₁ = -c₂. For n=3 this is the converse of the triangle inequality above. Suppose the Lemma is true for n = k ≥ 3. Let n = k+1, and sₖ = rₖ + rₖ₊₁. If sₖ≤ r₁, then applying the Lemma to r₁,...rₖ₋₁, sₖ and then splitting cₖ into (rₖ/sₖ)cₖ and (rₖ₊₁/sₖ)cₖ would prove it for n=k+1. If sₖ > r₁, then sₖ ≤ r₁ + r₂ ≤ r₁ +...+rₖ₋₁ and again we can apply the Lemma for n=k. QED

The degenerate case occurs when r₁ = r₂ +...+ rₙ in which the resulting polygon must have zero area (Fig. 3). The proof of Lemma 1 also shows that the edges of the polygon can be reordered and then arranged to look like a triangle, i.e. there is a partition of {rᵢ} into 3 subsets R₁, R₂ and R₃ such that sum of rⱼ in R₁ ≥ sum of rᵢ in R₂ ≥ sum of rₖ in R₃ and sum of rⱼ in R₁ ≤ sum of rᵢ in R₂ ∪ R₃. This is illustrated in Fig. 4.

overlapping edges

We have implicitly allowed the possibility that the edges of the polygon may overlap, i.e. the angles of the vertices are allowed to be 0 (see for example the degenerate case in Fig. 3. The next result shows that we can have up to n-3 angles to be either 0 or π radians.

Lemma 2 [Coppersmith and Hoffman, 2005]

Let rᵢ be real numbers such that r₁ ≥ r₂ ≥ ... ≥ rₙ ≥ 0 and r₁ ≤ ∑ᵢ>₁ rᵢ,, then there exists complex numbers cᵢ such that |cᵢ| = rᵢ and c₁ + c₂ + ... + cₙ = 0 and either all cᵢ's are real or n-2 of the cᵢ's are real.

Proof: We follow the proof in [Coppersmith and Hoffman, 2005]. Select j ≥ 3 to be the smallest number such that r₃ + ... + rⱼ ≥ r₁ - r₂. Such an index j is possible since r₃ + ... + rₙ ≥ r₁ - r₂. Since rᵢ ≤ r₂ for i ≥ 3 , this implies that r₃ + ... + rⱼ < r₁ as otherwise r₃ + ... + rⱼ₋₁ ≥ r₁ - r₂. For k = j+1,...,n, if r₃ + ... + rₖ₋₁ ≤ r₁, then set cₖ = rₖ, otherwise set cₖ = -rₖ. This ensures that r₁ - r₂ ≤ c₃ + ... + cₖ ≤ r₁ + r₂ for each k and by the converse of the triangular inequality there exists c₁ and c₂ with |c₁| = r₁ and |c₂| = r₂ such that r₁ + ... + rₙ = 0. Note that in the degenerate case both c₁ and c₂. QED

Singularity of matrices

The Lévy-Desplanques theorem (which is equivalent to Geršgorin's circle criterion) gives a sufficient condition for a complex matrix to be nonsingular:

Theorem 1

A complex matrix A = {aᵢⱼ} is nonsingular if |aᵢᵢ| > ∑ⱼ≠ᵢ |aᵢⱼ| for all i.

This is easily shown by using the generalized triangle inequality. Suppose A is singular, i.e. Ax = 0 for some nonzero vector x. Let i be such that |xᵢ|≥ |xⱼ| for all j. Since x≠0, this implies that |xᵢ| > 0. Then applying the generalized triangle inequality to |∑ⱼ≠ᵢ aᵢⱼ xⱼ| = |aᵢᵢxᵢ| results in |aᵢᵢ| |xᵢ| ≤ ∑ⱼ≠ᵢ |aᵢⱼ| |xⱼ|. Dividing both sides by |xᵢ| shows that it violates the condition that |aᵢᵢ| > ∑ⱼ≠ᵢ |aᵢⱼ| for all i. We have used the right zero eigenvector of A in this proof. The use of a left zero eigenvector of A to prove this result can be found in [Hoffman and Wu, 2016]. Similarly, the converse of the triangle inequality can be used to prove the following statement:

Theorem 2 [Camion and Hoffman, 1966]

Let A be a real nonnegative matrix and let D be a nonzero diagonal matrix with nonnegative diagonal elements. If the matrix B=DA satisfies bᵢⱼ ≤ ∑ₖ≠ᵢ bₖⱼ for all i, j, then there exists a complex singular matrix C = {cᵢⱼ} with |cᵢⱼ| = |aᵢⱼ|.

If dᵢ aᵢⱼ ≤ ∑ₖ≠ᵢ dₖaₖⱼ for all i, j then Lemma 1 implies that there are gᵢⱼ with |gᵢⱼ| = dᵢ aᵢⱼ such that ∑ᵢ gᵢⱼ = 0. By choosing cᵢⱼ = gᵢⱼ/dᵢ if dᵢ≠0 and cᵢⱼ = aᵢⱼ if dᵢ = 0, we get a matrix such that ∑ᵢ dᵢ cᵢⱼ = 0 and |cᵢⱼ | = aᵢⱼ . Since D is not the zero matrix, this implies that the rows of C = {cᵢⱼ} are linear dependent, hence C is singular.

These results were extended by the Camion-Hoffman theorem which gives necessary and sufficient conditions for a real matrix A such that any complex matrix whose elements have the same norm as the corresponding elements in A is nonsingular. More precisely it is stated as:

Theorem 3 [Camion-Hoffman Theorem]

Let A = {aᵢⱼ} be a real matrix of nonnegative numbers. The following conditions are equivalent:

1. If C = {cᵢⱼ} is a complex matrix with |cᵢⱼ| = aᵢⱼ then C is nonsingular.
2. If D is a nonzero diagonal matrix with nonnegative diagonal elements, then B = DA contains an entry bᵢⱼ such that bᵢⱼ > ∑ₖ≠ᵢ bₖⱼ.
3. There exists a permutation matrix P and a diagonal matrix D with positive diagonal elements such that B = PAD is strictly row sum dominant, i.e. bᵢᵢ > ∑ᵢ ≠ ⱼ bᵢⱼ.

If the conditions in Theorem 3 are not satisfied, then there is a candidate matrix C with |cᵢⱼ| = aᵢⱼ such that C is singular. Lemma 2 can be used to show that this candidate can be chosen such that each row is real except for possibly two elements.

Lemma 3 [Coppersmith and Hoffman, 2005]

If B is a singular complex matrix, then there exists a singular complex matrix C such that each row has either 0 or 2 complex elements and |bᵢⱼ| = |cᵢⱼ|.

Proof:

Suppose Bz = 0. As before, we select cᵢⱼ = bᵢⱼ zⱼ/|zⱼ| if zⱼ ≠ 0 and cᵢⱼ = |bᵢⱼ| otherwise. This means that ∑ⱼ cᵢⱼ|zⱼ| = 0, i.e. C is singular. By Lemma 2, we can replace up to n-2 of cᵢⱼ with real numbers of the same norm. QED

This result is extended to show that this candidate can be chosen with at most 2 complex elements:

Theorem 4 [Coppersmith and Hoffman, 2005]

If B is a singular complex matrix, then there exists a singular complex matrix C with either 0 or 2 complex elements such that |bᵢⱼ| = |cᵢⱼ|.

References:

P. Camion and A. J. Hoffman, "On the nonsingularity of complex matrices," Pacific Journal of Mathematics, vol. 17, no. 2, pp. 211-214, 1966.

D. Coppersmith and A. J. Hoffman, "On the singularity of matrices," Linear Algebra and its Applications, vol. 411, pp. 277-280, 2005.

L. Lévy, "Sur la possibilité du l’équilibre électrique," C. R. Acad. Sci. Paris, vol. 93, pp. 706-708, 1881.

J. Desplanques, "Théorème d’algébre," J. de Math. Spec., vol.9, pp. 12-13, 1887.

S. A. Geršgorin, "Über die abgrenzung der eigenwerte einer matrix," Izv. Akad. Nauk. USSR Otd. Fiz.-Mat. Nauk, vol. 7, pp. 749-754, 1931.

A. Hoffman and C. W. Wu, "Geršgorin variations IV: A left eigenvector approach," Linear Algebra and its Applications, vol. 498, pp. 136-144, 2016.