Figure 1: Illustration of the triangle inequality and its converse.
The triangle inequality is a workhorse in many branches of mathematics. It expresses the subadditivity of norms and is stated as:
||A+B|| ≤ ||A|| + ||B||
The name comes from its interpretation on the plane. If A and B are complex numbers, then we can draw a triangle with vertices at 0, A and A+B, with the resulting sides having norms equal to |A|, |B| and |A+B|. Stated in another way, if a, b and c are the lengths of the 3 sides of a triangle, then a ≤ b+c. This is illustrated in Fig. 1.
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.
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).
Figure 2: Illustration of the generalized triangle inequality and its converse.
A simple induction argument generalizes the triangle inequality to the summation of more than 2 quantities:
||A₁ + A₂ + ... + Aₙ|| ≤ ||A₁|| +||A₂|| + ... + ||Aₙ||
On the plane, the geometric interpretation is that if rᵢ are the lengths of edges of a polygon, then rᵢ ≤ ∑ⱼ≠ᵢ rⱼ or equivalently, if rᵢ are the lengths of edges of a polygon, and r₁ ≥ rᵢ, then r₁ ≤ ∑ᵢ>₁ rᵢ (Fig. 2).
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.
Figure 3: The degenerate polygon when r₁ = r₂ +...+rₙ .
Figure 4: The edges of the polygon can be reordered to form a triangle.
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
Figure 5: The edges of the polygon can be reordered and folded to form a triangle with the edges with lengths a and b being the longest 2 edges. Some of the edges may be overlapping.
The geometric interpretation of this result is that the polygon can be folded into a triangle (possibly with some overlapping edges and angles equals to 0 as illustrated in Fig. 5 with the edges with lengths a and b being the 2 longest edges.
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:
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.