Solving equations with real Jordan canonical forms

ABSTRACT

A new equivalent version of Gordan’s theorem of the alternative is presented based on the system of linear inequalities. Such a version has a more intuitive geometric interpretation than Gordan’s theorem. The real Jordan canonical form theorem is utilized in proving the theorem.

KEYWORDS:

• Gordan’s theorem
• real Jordan canonical form
• invariant subspace

PUBLIC INTEREST STATEMENT

This note examines whether a system of linear inequalities is solvable or a system of linear equations has a positive solution. In this note, we also investigated the geometrical properties of real linear operators by the use of its Jordan canonical form.

1. Introduction

Let ${\mathbb{R}}^n$ denote the set of vectors with size $n$, and ${\mathbb{R}}^{m\times n}$ denote the collection of $m$-by-$n$ real matrices. The following theorem examines circumstances under which a system of linear equations has a positive solution.

Theorem 1 (Gordan’s theorem). Let $A\in {\mathbb{R}}^{m\times n}$ be arbitrary. Then, either the system

(1.1) $Ax=0andx\ge 0$(1.1)

has a nonzero solution $x\in {\mathbb{R}}^n$, or the system

(1.2) $A^{T}y>0$(1.2)

has a solution $y\in {\mathbb{R}}^m$, but never both.

Theorem 1, due to Gordan (Gordan, 1873), has a long history and has been reproved numerous times. The survey by Kjeldsen (Kjeldsen, 2002) attributed the historical development of the theory of the systems of linear inequalities (1.1) and (1.2). It was rediscovered by Stiemke (Stiemke, 1915), representing a large class of theorems of the alternative that play an important role in linear and nonlinear programming. Such theorems are crucial in deriving optimality conditions for wide classes of extremal problems. For more background information and applications on the theorems of the alternative and other relevant matters, we refer to the textbooks (Ciarlet, 1989; Gill et al., 1991; Mccormick, 1983; Osborne, 1985), the surveys (Dax, 1993; Saunders & Schneider, 1979), and research papers (Dax & Sreedharan, 1997; Galán, 2017; Giannessi, 1984; Mangasarian, 1981).

Gordan (Gordan, 1873) and Stiemke (Stiemke, 1915) proved Theorem 1 by induction independently. However, they did not give any motivation for this investigation. Such an investigation do not make clear why the theorem works; see e.g. (Gale, 1960). Recent proofs are usually based on separation theorems of the convex sets with a simple geometrical interpretation. In this note, we present a simple self-contained proof which is based on elementary arguments in linear algebra.

The paper is organized as follows. In the next section, we will present a new equivalent form of Theorem 1. And in Section 3, we will give a simple, elementary proof of the equivalent form by the use of the real Jordan canonical form. The last section contains conclusions and some remarks.

2. An equivalent form

Let $r$ denote the rank of the matrix $A$. Clearly, one has

$r\le min\{m,n\}.$

For the sake of avoiding trivial cases, we always assume that $r$ is greater than zero. By the theory of the linear algebra (Wilkinson & Reinsch, 1971), there is an invertible matrix $M\in {\mathbb{R}}^{m\times m}$ and a permutation matrix $P\in {\mathbb{R}}^{n\times n}$ such that

(2.1) $MA=\left(\begin{array}{cc}I& B\\ 0& 0\end{array}\right)P,$(2.1)

where $B$ is a $r$-by-$(n-r)$ real matrix, and $I$ denotes a unit matrix with a suitable size. The left product is equivalent to performing a series of elementary row operations on the matrix $A$. Then the system of equations in (1.1) can be rewritten as follows:

(2.2) $\left(\begin{array}{cc}I& B\\ 0& 0\end{array}\right)Px=0.$(2.2)

If $\left(\begin{array}{c}u\\ v\end{array}\right)=Px$, where $u\in {\mathbb{R}}^r$ and $v\in {\mathbb{R}}^{n-r}$, then $x\ge 0$ means that both $u\ge 0$ and $v\ge 0$ hold. This results in our main theorem, an equivalent algebraic version of Gordan’s theorem (Theorem 1).

Theorem 2. (The Main Theorem). Let $B\in {\mathbb{R}}^{r\times n_1}$ be arbitrary. Then, either the system

(2.3) $Bv\le 0andv\ge 0$(2.3)

has a nonzero solution $v\in {\mathbb{R}}^{n_1}$, or the system

(2.4) $B^{T}y>0andy>0$(2.4)

has a solution $y\in {\mathbb{R}}^r$, but never both.

From this it is simple to prove Gordan’s theorem (Theorem 1). Our main theorem has a more intuitive geometric interpretation than Gordan’s theorem in the sense discussed below but despite this is perhaps simpler to prove.

In the following statement, we assume without loss of generality that $r=n_1$, i.e. the matrix $B$ is square (if not, make it a square matrix by adding zero rows or columns).

Let ${\mathbb{R}}_{++}^r$ and ${\mathbb{R}}_{+}^r$ denote the positive and the nonnegative quadrant cones, respectively, that is,

${\mathbb{R}}_{++}^r=\{v\in {\mathbb{R}}^r|v>0\}\mathrm{a}\mathrm{n}\mathrm{d}{\mathbb{R}}_{+}^r=\{v\in {\mathbb{R}}^r|v\ge 0\}.$

If $\mathcal{B}$ is a linear operator represented by the matrix $B$, then the solvability of the system (2.3) is equivalent to that

(2.5) $\mathcal{B}({\mathbb{R}}_{+}^r)\cap (-{\mathbb{R}}_{+}^r)\ne \mathrm{\varnothing },$(2.5)

while the solvability of the system (2.4) is equivalent to that

(2.6) ${\mathcal{B}}^{\ast }({\mathbb{R}}_{++}^r)\cap {\mathbb{R}}_{++}^r\ne \mathrm{\varnothing },$(2.6)

where ${\mathcal{B}}^{\ast }$ is the adjoint operator of $\mathcal{B}$, and it can be represented by the matrix $B^T$ when $B$ is a real matrix.

3. Proofs

The Jordan canonical form is described with reference to matrices known as elementary Jordan blocks. An elementary Jordan block of size $l\times l$ associated with an eigenvalue $\lambda$ will be denoted by $J_l(\lambda )$, and its general form is adequately illustrated by the definition

(3.1) $J_l(\lambda )=\left(\begin{array}{cccccc}\lambda & 1& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\\ \hspace{0.17em}& \lambda & 1& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \ddots & \ddots & \hspace{0.17em}& \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \lambda & 1& \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \lambda & \hspace{0.17em}\end{array}\right).$(3.1)

The basic theorem is that given any $r\times r$ matrix with complex entries, there exists a nonsingular matrix $S$ such that

(3.2) $SB{S}^{-1}=J,SB=JS,$(3.2)

where $J$, the Jordan canonical form of $B$, is block diagonal, each diagonal matrix being an elementary Jordan block with $\lambda ={\lambda }_i$. Apart from the ordering of the blocks along the diagonal of $J$ (which can be arbitrary), the Jordan canonical form is unique, although $S$ is far from unique.

Following we mainly consider the Jordan canonical form when the matrix $B$ has only real entries. In this case, all the nonreal eigenvalues must occur in conjugate pairs. Moreover, if $\xi +i\eta$ is an eigenvector of the real matrix $B$ associated with the complex eigenvalue $\lambda =a+bi$, then $\xi -i\eta$ must be an eigenvector of $B$ associated with the conjugate eigenvalue $\bar{\lambda }=a-bi$, where $a,b\in \mathbb{R}$, $\xi ,\eta \in {\mathbb{R}}^r$ and $i$ is the imaginary unit, i.e. $i^2=-1$. That is

$B(\xi +i\eta )=(a+bi)(\xi +i\eta )andB(\xi -i\eta )=(a-bi)(\xi -i\eta ),$

or equivalently,

$B(\xi ,\eta )=(\xi ,\eta )\left(\begin{array}{cc}a& b\\ -b& a\end{array}\right),$

in which the right $2\times 2$ real matrix, denoted by $C(a,b)$, has eigenvalues $a\pm bi$. If $\theta =arcsin\frac{b}{a^2+b^2}$, then

$C(a,b)=(a^2+b^2)\left(\begin{array}{cc}cos\theta & sin\theta \\ -sin\theta & cos\theta \end{array}\right).$

So the linear operator represented by the matrix $C(a,b)$ on the real space $span\{\xi ,\eta \}$ is a superposition of rotation and stretching. Of course, the rotation angle of the corresponding adjoint operator, represented by the matrix $C^T(a,b)$, is the opposite of the rotational angle of $C(a,b)$. When $\theta \ne 0$ or $\pi$, such two linear operators have no eigenvector on the $2$-dimensional real space $span\{\xi ,\eta \}$.

Note that the structure of the Jordan blocks corresponding to the conjugate eigenvalue $\bar{\lambda }$ must be the same as the structure of the Jordan blocks corresponding to the eigenvalue $\lambda$, e.g. see, (Horn & Johnson, 1990). For example, if $\lambda$ is a complex eigenvalue of the real matrix $B$, and if $J_2(\lambda )$ appears in the Jordan canonical form of $B$ with a certain multiplicity, $J_2(\bar{\lambda })$ must also appear with the same multiplicity. Then, the block matrix

$\left(\begin{array}{cc}{J}_2(\lambda )& 0\\ 0& J_2(\bar{\lambda })\end{array}\right)=\left(\begin{array}{cccc}\lambda & 1& 0& 0\\ 0& \lambda & 0& 0\\ 0& 0& \bar{\lambda }& 1\\ 0& 0& 0& \bar{\lambda }\end{array}\right)$

is permutation similar to the block matrix

$\left(\begin{array}{cccc}\lambda & 0& 1& 0\\ 0& \bar{\lambda }& 0& 1\\ 0& 0& \lambda & 0\\ 0& 0& 0& \bar{\lambda }\end{array}\right).$

If $\lambda =a+bi$ and $\bar{\lambda }=a-bi$, then it is also similar to the matrix

$\left(\begin{array}{cc}C(a,b)& I\\ 0& C(a,b)\end{array}\right).$

In general, each block pair of conjugate $l$-by-$l$ Jordan block

$\left(\begin{array}{cc}{J}_l(\lambda )& 0\\ 0& J_l(\bar{\lambda })\end{array}\right)$

with nonreal $\lambda =a+bi$ is similar to a real $2l$-by-$2l$ block of the form

(3.3) $C_l(a,b)=\left(\begin{array}{cccccccc}C(a,b)& I& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\\ \hspace{0.17em}& C(a,b)& \ddots & \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \ddots & I& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\\ \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& C(a,b)& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}& \hspace{0.17em}\end{array}\right).$(3.3)

These observations lead us to the real Jordan canonical form, see, (Horn & Johnson, 1990).

Theorem 3. Each real matrix $B\in {\mathbb{R}}^{r\times r}$ is similar to a block diagonal real matrix of the form

(3.4) $\begin{array}{rl}& J_R=diag(C_{r_1}(a_1,b_1),n,C_{r_p}(a_{r_p},b_{r_p}),J_{r_{p+1}}({\lambda }_{p+1}),\cdots ,J_{r_k}\\ & ({\lambda }_k)),\end{array}$(3.4)

where ${\lambda }_j=a_j+b_{j}i$ is a nonreal eigenvalue of $B$ for $j=1,2,\cdots ,p$, $a_j,b_j$ are real, ${\lambda }_{p+1},\cdots ,{\lambda }_k$ are real eigenvalues of $B$. The real Jordan block $C_{r_j}(a_j,b_j)$ is of the form (3.3), and the Jordan block $J_{r_j}({\lambda }_j)$ are exactly the Jordan blocks in (3.2) with $\lambda ={\lambda }_j$.

The motivation to prove our main theorem drives us to investigate the connection between the real Jordan canonical forms of the real matrix $B$ and its transpose. A simple observation is that if the real matrix $B$ has a real Jordan canonical form $J_R$, then its transpose has a real Jordan canonical form $J_R^T$. This yields the following result.

Corollary 4. Let the real Jordan canonical form $J_R$ of the real matrix $B$ be defined by (3.4).

(1) If ${\zeta }_j$ is an eigenvector of $B^T$ associated with the Jordan block $J_{r_j}^T({\lambda }_j)$, then

$W_j(B)=span\{{\zeta }_j,B{\zeta }_j,B^2{\zeta }_j,\cdots ,B^{r_j-1}{\zeta }_j\}$

is an invariant subspace of $\mathcal{B}$, in which $\mathcal{B}$ has one linearly independent real eigenvector on $W_j(B)$;

(2) If ${\xi }_j\pm i{\eta }_j$ are eigenvectors of $B^T$ on the complex space ${\mathbb{C}}^r$ associated with the real Jordan block $C_{r_j}^T(a_j,b_j)$, where ${\xi }_j,{\eta }_j\in {\mathbb{R}}^r$, then

$W_j(B)=span\{{\xi }_j,{\eta }_j,B{\xi }_j,B{\eta }_j,\cdots ,B^{r_j-1}{\xi }_j,B^{r_j-1}{\eta }_j\}$

is an invariant subspace of $\mathcal{B}$ on ${\mathbb{R}}^r$;

(3) ${\mathbb{R}}^r$ is a direct sum of the subspaces $W_j(B),j=1,2,\cdots ,k$, i.e.

(3.5) ${\mathbb{R}}^r=W_1(B)\oplus W_2(B)\oplus \cdots \oplus W_k(B).$(3.5)

Proof. If $r_j=1$, then the result is trivial. Otherwise, each Jordan block $J_{r_j}({\lambda }_j)$ and its transpose $J_{r_j}^T({\bar{\lambda }}_j)$ have only one linearly independent real eigenvector $e_{r_j}$ and $e_1$, respectively, where $e_{r_j}$ and $e_1$ denote the last column and the first column of the unit matrix with order $r_j$. Then, it is easy to verify that the above results for the real Jordan canonical form $J_R$ hold. Then, the desired results hold since the similarity invariance of the subspaces $W_j(J)$.□

If the real matrix $B$ in Corollary 4 is replaced by its transpose, then the corresponding result also is true. We may obtain another decomposition of ${\mathbb{R}}^r$ in the form of the matrix $B^T$

(3.6) ${\mathbb{R}}^r=W_1(B^T)\oplus W_2(B^T)\oplus \cdots \oplus W_k(B^T).$(3.6)

Of course, we have $W_j(B^T)=W_j(B)$ for all $j=1,2,\cdots ,k$.

It follows from Corollary 4 that if $g_j$ and $V_{{\lambda }_j}(B^T)$ denote the geometric multiplicity and the eigensubspace of ${\lambda }_j$ associated with the matrix $B^T$, then the null space of $(B-\lambda I{)}^{g_j}$ is equal to

$span\{V_{{\lambda }_j}^T,B{V}_{{\lambda }_j}(B^T),\cdots ,B^{g_j-1}{V}_{{\lambda }_j}(B^T)\}.$

In addition, the first and last terms of Corollary 4 is still true when $B$ is a complex matrix, only if the transpose matrix $B^T$ is replaced by the conjugate transpose matrix $B^{\ast }$, and the corresponding Jordan block $J_{r_j}^T({\lambda }_j)$ is replaced by $J_{r_j}^T({\bar{\lambda }}_j)$.

Let

$V_j^{+}(B)=span\{{\xi }_j+i{\eta }_j,B({\xi }_j+i{\eta }_j),\cdots ,B^{r_j}({\xi }_j+i{\eta }_j)\}$

and

$V_j^{-}(B)=span\{{\xi }_j-i{\eta }_j,B({\xi }_j-i{\eta }_j),\cdots ,B^{r_j}({\xi }_j-i{\eta }_j)\}$

be invariant subspaces of $\mathcal{B}$, where ${\xi }_j\pm i{\eta }_j$ are eigenvalues of $B^T$ associated with the eigenvalues $a_j\pm b_{j}i$. Then ${\xi }_j\pm i{\eta }_j\in V_j^{+}(B)\oplus V_j^{-}(B)$ such that $\mathcal{B}$ on one 2-dimensional real subspace $V=span\{\xi ,\eta \}\subset W_j(B)$ rotates the angles ${\theta }_j=arcsin\frac{b_j}{a_j^2+b_j^2}$, while the adjoint operator ${\mathcal{B}}^{\ast }$ on the subspace $V_j\subset W_j\left(B^T\right)$ rotates the angles $-{\theta }_j$.

Now we ready to Theorem 2.

Proof of the main theorem. It is easy to show that both two inequalities (2.5) and (2.6) cannot be true together. From Corollary 4, we only need prove that at least one of them holds for each $W_j=W_j(B)=W_j(B^T)$, $j=1,2,\cdots ,k$. The proof requires consideration of two cases.

When the eigenvalue ${\lambda }_j$ is a real number, the inequality (2.6) holds on $W_j$ if and only if ${\lambda }_j>0$, while the inequality (2.5) holds on $W_j$ if and only if ${\lambda }_j\le 0$.

When the eigenvalue ${\lambda }_j=a_j+b_{j}i$ is a complex number, the inequality (2.6) holds on $W_j$ if and only if $0^0<arcsin\frac{b_j}{a_j^2+b_j^2}<{90}^0$, while the inequality (2.5) holds on $W_j$ if and only if ${90}^0\le arcsin\frac{b_j}{a_j^2+b_j^2}\le {180}^0$. The proof is finished.$$

Finally, Gordan’s theorem follows from our main theorem trivially.

4. Concluding remarks

In this note, we have given an alternative proof of Gordan’s theorem, a proof that is based on the real Jordan canonical form. Another purely algebraic ways are to apply the property of the orthogonal or antisymmetric matrix. See, for example, (Broyden, 1998) and (Tucker, 1956; Vajda, 1961). This approach still don’t make clear why the theorem works. In our proof, a new geometrical interpretation for a pair of real linear adjoint operators is presented.

Other theorems of the alternative seem to be also related to the above geometrical interpretation. This will be our further work.

Acknowledgements

This study was funded by the National Natural Science Foundation of China (11871118). The author has received research grants from Yangtze University. The author declares that he has no conflict of interest. The author is indebted to the anonymous referees, whose detailed remarks helped in improving the manuscript.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

Supported by the National Natural Science Foundation of China (11871118).

Notes on contributors

Zi-Zong Yan

Zi-Zong Yan is currently a professor in the school of information and mathematics at Yangtze university. He received his Ph.D. degree in the school of mathematics and statistics from Wuhan university in 2005. His current research interests are in the area of optimization theory and matrix analysis.

Zhi-Jia Shu

Zhi-Jia Shu was born in Hubei, China, in 1995. He received his Bachelor’s degree in the school of information and mathematics at Yangtze university, in 2019. Currently, he is a master in reading at Yangtze university. His research interest is optimization theory.