The triangle inequality and its converse

The triangle inequality

The triangle inequality is a workhorse in many branches of mathematics. It expresses the subadditivity of norms and is stated as:
$$ \| A+B\| \leq \|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 the points $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 \leq b+c$. This is illustrated in Fig. 1.
A slightly different, but clearly equivalent statement is the following: if $a \geq b \geq c \geq 0$ are the lengths of the $3$ sides of a triangle, then $a \leq b+c$. We will use this alternative formulation as it is easier to state and prove the converse and its generalization.

Fig. 1: Illustration of the triangle inequality and its converse.

Converse of the triangle inequality on the plane

The converse of the triangle inequality is also true: If $a \geq b \geq c \geq 0$ and $a \leq b+c$, then there exists a triangle whose sides have lengths $a$, $b$ and $c$ respectively. Equivalently this can be restated as: If $a \geq b \geq c \geq 0$ and $a \leq 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 this triangle.
First we show that $d = \frac{b^2+c^2 - a^2}{2bc}$ satisfies $|d| \leq 1$. This follows from the fact that $d = \frac{(b+c)^2 -a^2-2bc}{2bc} = -1 + \frac{(b+c)^2 - a^2}{2bc} \geq -1$
and $d= \frac{(b-c)^2 -a^2+2bc}{2bc} = \frac{(b-c)^2 -a^2}{2bc} + 1\leq 1$.
Thus we can choose $\phi = \cos^{-1}(d)$ which satisfies $a^2 = b^2+c^2-2bc\cos (\phi)$ and the law of cosines shows that the triangle with sides of length $b$ and $c$ and angle $\phi$ with have the third side of length $a$. (see Fig. 1).

The generalized triangle inequality and its converse

A simple induction argument generalizes the triangle inequality to the summation of more than 2 quantities:
$$\left\| \sum_i^n A_i\right\| \leq \sum_i^n \|A_i\|$$
The geometrical interpretation is that if $r_i$ are the lengths of edges of a polygon, then $r_i \leq \sum_{j\neq i} r_j$ or equivalently, if $r_i$ are the lengths of edges of a polygon, and $r_1\geq r_i$, then $r_1\leq \sum_{i > 1}r_i$ (Fig. 2).

Fig. 2: Illustration of the generalized triangle inequality and its converse.

The converse of the generalized triangle inequality is true as well. If $r_1\geq r_i \geq 0$ and $r_1\leq \sum_{i = 2}^n r_i$, then there is a $n$-polygon with $r_i$ as the lengths of its sides (Fig. 2). Having one vertex of the polygon at the origin of the complex plane this can be reformulated as:

Lemma 1: (Ref. [1])
Let $n\geq 2$ and $r_1\geq r_2\geq \cdots r_n \geq 0$ be real sumbers such that $r_1 \leq \sum_{i=2}^n r_i$, then there exists complex numbers $c_i$ such that $|c_i| = r_i$ and $\sum_i c_i = 0$.

Proof: 
As stated in [1] this is easily proved by induction. For $n=2$ this implies that $|r_1| = |r_2|$ and thus we can set $c_1 = r_1 = -c_2$. For $n=3$ this is the converse of the triangle inequality described above. Suppose the Lemma is true for $n = k \geq 3$. Let $n = k+1$, and $s_k = r_k+r_{k+1}$. If $s_k \leq r_1$, then applying the Lemma to $r_1,\cdots r_{k-1}, s_k$ and then splitting $c_k$ into $\frac{r_k}{s_k}c_k$ and $\frac{r_{k+1}}{s_k}c_k$ would prove it for $n=k+1$. If $s_k > r_1$, then $s_k \leq r_1 + r_2 \leq \sum_{i=1}^{k-1} r_k$ and again we can apply the Lemma for $n=k$.


The degenerate case occurs when $r_1 = \sum_{i=2}^n r_i$ in which the resulting polygon must have zero area (Fig. 3). The proof of Lemma 1 also shows that the polygon can be arranged to look like a triangle, i.e. there is a partition of $\{r_i\}$ into $3$ sets $R_1$, $R_2$ and $R_3$ such that $\sum_{r_i\in R_1}r_i \geq \sum_{r_j\in R_2}r_j \geq \sum_{r_k\in R_3}r_k $ and $\sum_{r_i\in R_1}r_i \leq \sum_{r_j\in R_2\cup R_3}r_j $. This is illustrated in Fig. 4.

Fig. 3: The degenerate polygon when $r_1 = \sum_{i=2}^n r_i$.

Fig. 4: The edges of the polygon can be reordered to form a triangle.

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 $\pi$.


Lemma 2: (Ref. [2])
Let $r_i$ be real numbers such that $r_1\geq r_2 \geq \cdots \geq r_n \geq 0$ and $r_1 \leq \sum_{i=2}^n r_i$, then there exists $c_i$ such that $|c_i| = r_i$ and $\sum_i c_i = 0$ and either all $c_i$'s are real or $n-2$ of the $c_i$'s are real.

Proof:
We follow the proof in [2]. Select $j\geq 3$ to be the smallest number such that $\sum_{i=3}^j r_i \geq r_1-r_2$. Such an $j$ is possible since $\sum_{i=3}^n r_i \geq r_1-r_2$. Since $r_i\leq r_2$ for $i\geq 3$, this implies that $\sum_{i=3}^j r_i < r_1$ as otherwise $\sum_{i=3}^{j-1} r_i \geq r_1-r_2$. For $k = j+1,\dots n$, if $\sum_{i=3}^{k-1} r_i \leq r_1$, then set $c_k = r_k$, otherwise set $c_k = -r_k$. Ths ensures that $r_1-r_2\leq \sum_{i=3}^k c_i \leq r_1+r_2$ for each $k$ and by the converse of the triangular inequality there exists $c_1$ and $c_2$ with $|c_1| = r_1$ and $|c_2| = r_2$ such that $\sum_i c_i = 0$. Note that in the degenerate case both $c_1$ and $c_2$ are real.


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.

Fig. 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.

Singularity of matrices

The Levy-Desplanques theorem [3,4] (which is equivalent to Gershgorin's circle criterion [5]) gives a sufficient condition for a complex matrix to be nonsingular:

Theorem 1
The matrix $A = \{a_{ij}\}$ is nonsingular if $|a_{ii}| > \sum_{j\neq i}|a_{ij}|$ for all $i$.

This is easily shown by using the generalized triangle inequality. Suppoe $A$ is singular, i.e. $Ax = 0$ for some nonzero vector $x$.
Let $i$ be such that $|x_i|\geq |x_j|$ for all $j$. Since $x\neq 0$, this implies that $|x_i| > 0$. Then applying the generalized triangle inequality to $|\sum_{j\neq i}a_{ij}x_j| = |a_{ii}x_i|$ results in:
$$ |a_{ii}||x_i| \leq \sum_{j\neq i}|a_{ij}||x_i|$$
Dividing both sides by $|x_i|$ shows that it violates the condition that $|a_{ii}| > \sum_{j\neq i}|a_{ij}|$ for all $i$.

Similarly, the converse of the triangle inequality can be used to prove the following statement:

Theorem 2: (Ref. [1])
Let $A$ be a real nonnegative matrix and let $D$ is a nonzero diagonal matrix with nonnegative diagonal elements. If $B=DA$ satisfies $b_{ij}\leq \sum_{k\neq i} b_{kj}$ for all $i$, $j$, there there exists a complex singular matrix $C = \{c_{ij}\}$ with $|c_{ij}| = a_{ij}$.

If $d_ia_{ij}\leq \sum_{k\neq i} d_ka_{kj}$ for all $i$, $j$, then Lemma 1 implies that there are $g_{ij}$ with $|g_{ij}| = d_ia_{ij}$ such that $\sum_i{g_{ij}} = 0$.
By choosing $c_{ij} = \frac{g_{ij}}{d_i}$ if $d_i \neq 0$ and $c_{ij} = a_{ij}$ if $d_i = 0$, we get a matrix such that $\sum_i d_ic_{ij} = 0$ and $|c_{ij}| = a_{ij}$. Since $D$ is not the zero matrix, this implies that the rows of $\{c_{ij}\}$ are linear dependent, hence $C$ is singular.


These results were extended by the Camion-Hoffman theorem [1] 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)
Let $A = \{a_{ij}\}$ be a real matrix of nonnegative numbers. The following conditions are equivalent:

1. If $C = \{c_{ij}\}$ is a complex matrix with $|c_{ij}| = a_{ij}$ then $C$ is nonsingular.
2. If $D$ is a nonzero diagonal matrix with nonnegative diagonal elements, then $B = DA$ contains an entry $b_{ij}$ such that $b_{ij} >\sum_{k\neq i} b_{kj}$.
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_{ii} >\sum_{i\neq j} b_{ij}$.

If the conditions in Theorem 3 are not satisfied, then there is a candidate matrix $C$ with $|c_{ij}| = a_{ij}$ 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: (Ref. [2])
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_{ij}| = |c_{ij}|$.

Proof:
Suppose $Bz = 0$. As before, we select $c_{ij} = \frac{b_{ij}z_j}{|z_j|}$ if $z_j\neq 0$ and $c_{ij} = |b_{ij}|$ otherwise, i.e. $\sum_i c_i = 0$. This means that $\sum_i c_{ij}|z_j| = 0$, i.e. $C$ is singular. By Lemma 2, we can replace up to $n-2$ of $c_{ij}$ with real numbers of the same norm.

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

Theorem 4: (Ref. [2])
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_{ij}| = |c_{ij}|$.

References
[1] P. Camion and A. J. Hoffman, "On the nonsingularity of complex matrices," Pacifi c Journal of Mathematics, vol. 17, no. 2, pp. 211-214, 1966.
[2] D. Coppersmith and A. J. Hoffman, "On the singularity of matrices," Linear Algebra and its Applications, vol. 411, pp. 277-280, 2005.
[3]  L. Lévy, "Sur la possibilité du l'équilibre électrique," C. R. Acad. Sci. Paris, vol. 93, pp. 706-708, 1881.
[4] J. Desplanques, "Théorème d'algèbre," J. de Math. Spec., vol. 9, pp. 12-13, 1887.
[5] S. A. Geršgorin, "Über die Abgrenzung der Eigenwerte einer Matrix," Izv. Akad. Nauk SSSR Otd. Fiz.-Mat. Nauk, vol. 7, pp. 749-754, 1931.