Tuesday, October 10, 2017

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.








Friday, September 8, 2017

Numbers such that 7 is the smallest decimal digit of their squares.

9949370777987917 is the smallest number whose square has as its smallest decimal digit 7.
Note that $9949370777987917^2 = 98989978877879888789778997998889$. What is the next such number?

Sunday, July 23, 2017

Solar eclipse 2017

On August 21, 2017, there will be a solar eclipse occurring coast to coast across the continental United States. The last time this happened was almost a century ago in 1918. This has two effects on states that generate a lot of solar energy: the solar energy generated decreases during an Eclipse and people turn on their lights as the sky darkens. Both of these events stress the utility grid.  California's utilities are asking people not to turn on the lights during this event. I am surprised such a short event (and California is not even in the path of totality) can cause concerns for power utilities operators. I wonder if something similar happens when there is no wind in the summer and more people turn on their fans to cool off?

Monday, July 17, 2017

Happy Yellow Pig Day!

Today, July 17 is Yellow Pig Day. This "holiday" was created by Princeton math students Michael Spivak and David C. Kelly when they were analyzing the number 17 and wanted to have a day to celebrate this number. This year (2017) is extra special since the year also ends in the digits 17.
Michael Spivak is the author of the wonderful differential geometry texts (published by Publish-or-Perish Press which he founded) which I fondly remember reading in graduate school. He also wrote a popular typesetting book on TeX which I did not read since Leslie Lamport's book on LaTeX makes typesetting papers using LaTeX so easy that I have skipped learning TeX and went straight to using LaTeX (which sits on top of TeX).
If I remember correctly, the typesetting software I used prior to LaTeX was ChiWriter, which is quite easy to use as it is WYSIWYG, so moving to a typesetting paradigm where you relinquish control on the formatting, page breaks, etc. to the software is quite unnerving, but I soon learn to appreciate it as I can focus on the content of the document, rather than spend time improving its appearance.

Sunday, June 4, 2017

Moon and Jupiter on June 3, 2017

The Moon and Jupiter are in close proximity (not physically, but as viewed from Earth) on the night of June 3, 2017.

Sunday, May 21, 2017

The race of Cloud Computing

I wrote earlier about a news digest app returning supplemental information which is not directly related to the article. Today, I read on the app that the horse "Cloud Computing" has won the Preakness race. And sure enough, there is a box underneath the article with a definition of cloud computing from Wikipedia. What is ironic is that this news summary is probably enabled by leveraging cloud computing. "Cloud Computing" won over "Classic Empire" by coming in from behind and won the race by a head. Perhaps this is an indication how cloud computing will overtake the classical empire of on premise computing😊.

Thursday, May 11, 2017

Find interesting properties of your favorite number

I created a simple web application where you can enter a positive integer < 1012 , wait a few moments and it will return a list of interesting properties about this number. Please give it a try and let me know what you think!

To start, please visit: http://postvakje.pythonanywhere.com/

Sunday, May 7, 2017

Spring is here, pt. 2


House Finch


Chipping Sparrow
My wife says it reminds her of Red from Angry Birds

Tuesday, May 2, 2017

12345

The number 12345 is interesting as it is a sphenic number (product of 3 distinct primes) and its digit reversal 54321 is also a sphenic number.

Tuesday, April 18, 2017

Palindromic primes which are sums of 3 consecutive primes

OEIS sequence A113846 lists palindromic primes $q$ which are the sums of 3 consecutive primes $p_1$, $p_2$, $p_3$ such that $p_2$ is also a palindromic prime.

Theorem: All terms of A113846 have an odd number of digits and the first digit (and last digit) is either 3 or 9. In addition, $p_2$ and $p_3$ have the same first digit and $p_2$ and $p_3$ have the same number of digits as $q$. The first digit of $p_2$ (and $p_3$) is equal to the first digit of $q$ divided by 3, i.e. if the first digit of $q$ is $3$, then the first digit of $p_2$ and $p_3$ is $1$.

Proof: First note that all palindromes with an even number of digits is divisible by 11. Let $p_1$, $p_2$, $p_3$ be 3 consecutive primes such that $p_2$ is a palindrome and $q = p_1+p_2+p_3$ is a palindromic prime.  It is clear that $q, p_2 > 11$ and have a odd number of digits since the first term of A113846 is 31513.
The first digit of $p_2$ cannot be 2 since $p_2$ is odd. Next we show that the first digit of $p_2$ is either 1 or 3.
Let $k$ be an even integer such that $p_2$ has $k+1$ digits. Suppose the first digit of $p_2$ is 4 or larger, i.e. $4\cdot 10^k \leq p_2 < 10^{k+1}$. Then by Bertrand's postulate (or Bertrand-Chebyshev theorem), $p_1\geq \frac{p_2}{2}$ and $p_3 \leq 2p_2$. This implies that $10^{k+1} > p_1 \geq 2\cdot 10^k$, $4\cdot 10^k < p3 \leq 2\cdot 10^{k+1}$ and thus $10^{k+1} < q < 4\cdot 10^{k+1}$, i.e. $q$ has an even number of digits, a contradiction.
Next we show that the first digit of $q$ is 3 or 9. To do this, we need a stronger result than Bertrand's postulate for the prime gap. Since $p_2 > 647$, Rohrback and Weis's 1964 result [1] shows that $p_1 \geq \frac{12}{13}p_2$ and $p_3 \leq \frac{14}{13}p_2$.
This shows that $2\frac{12}{13} p_2 \leq q \leq 3\frac{1}{13} p_2$. Since $q$ is prime, it cannot start with the digit 5. If $p_2$ start with the digit 1, then $2\cdot 10^k \leq q \leq 6 \frac{2}{13} 10^k$ and thus $q$ must start with the digit 3.
If $p_2$ start with the digit 3, then $8\frac{10}{13}10^k \leq q \leq 12\frac{4}{13}10^k$. Since $q < 10^{k+1}$, this means that $q$ must start with the digit 9.
Clearly $p_3$ must have the same number of digits as $p_2$ and as $q$.
Finally, we show that $p_3$ has the same starting digit as $p_2$. Suppose $p_2$ starts with the digit 1. If $p_3$ has a different starting digit, this must mean that $p_3 \geq 2\cdot 10^k$, i.e.
$p_2 \geq 1\frac{11}{13}10^k$, $p_1\geq 1\frac{119}{169} 10^k$ and $q \geq 4\cdot 10^k$, a contradiction.
Suppose $p_2$ start with the digit 3. If $p_3$ has a different starting digit, this must mean that $p_3 \geq 4\cdot 10^k$, i.e.
$p_2 \geq 3\frac{9}{13} 10^k$, $p_1 \geq 3\frac{69}{169}10^k$ and $q\geq 10^{k+1}$, a contradiction. QED

This argument also shows that to search for terms, for each $k$, one only needs to consider for $p_2$ the palindromic primes in the ranges $(10^k, 1\frac{7}{19}10^k)$ and $(3\cdot 10^k, 3 \frac{8}{19}\cdot 10^k)$ which amount to approximately $0.79\cdot 10^{\frac{k}{2}}$ palindromes to consider rather than a full search of $10\cdot 10^{\frac{k}{2}}$ palindromes of length $k+1$.

Conjecture: For all terms in A113846, the corresponding primes $p_1$ has the same number of digits and the same first digit as $p_2$ and $p_3$.

References:
1. H. Rohrback and J. Weis, "Zum finiten Fall des Bertrandschen Postulats", J. Reine Angew. Math., 214/215 (1964), 432–440.