Some Useful Theorems

Back

We now state a set of useful theorems with proofs omitted.

Theorem: (Fundamental Theorem of Algebra) an algebraic expression of the polynomial form:

a_nl ⁿ + a_n-1l ^n-1 + .... + a_2l ² + a_1l + a₀ = 0

where a₀ ¹ 0, has exactly n complex or real roots l ₁, ..., l _n (repetition is, of course, possible).

Theorem: If the coefficients of a polynomial (a₁, a₂, etc.) are real, then any complex roots will come in conjugate pairs, i.e. l = u ± iv where i is the imaginary operator i =Ö -1 and u and v are real numbers, so that u is the "real part" of l (i.e., Re(l ) = u) and v the "imaginary part" of l (i.e. Im(l ) = v).

Theorem: (Descartes's Rule of Signs) Let a₀, ..., a_n be the sequence of coefficients in a polynomial and let k be the total number of "changes of sign" from one coefficient to the next in that sequence. Then the number of positive real roots of the polynomial is equal to k minus a positive even number. (note: if k = 1, then there is exactly one positive real root).

We now turn to the Perron-Frobenius theorems on non-negative square matrices.  They are of two types: one for the general case (I), the other for the irreducible case (II).

Theorem: (Perron-Frobenius I) If A is a non-negative square matrix then the following hold:

(a) A has a non-negative real eigenvalue

(b) no real eigenvalue of A can have an absolute value larger than the largest real eigenvalue l _m

(c) at least one right eigenvector and one left eigenvector associated with l_m are semipositive.

(d) [l I - A]^-1 >> 0 for each l > l_m

(e) l _m is a nondecreasing function of each of the elements of matrix A.

Theorem: (Perron-Frobenius II) If A is an irreducible non-negative square matrix then the following hold:

(a) A has a positive maximum eigenvalue l_m

(b) the right eigenvector x associated with l_m is positive, i.e. for Ax = l_mx, x > 0.

(c) the left eigenvector x¢ associated with l _m is also positive, i.e. x¢ A = x¢ l _m, x¢ > 0.

(d) if l is any eigenvalue of A, then |l | £ l_m

(e) l _m is a continuous increasing function of the elements in A.

(f) the maximum eigenvalue for any submatrix of A is smaller than the maximum eigenvalue for A.

(g) To each real eigenvalue l of A different from l _m, there corresponds an eigenvector x ¹ 0 such which has at least one negative component.

(h) Given a real number m = (1/n ) > 0, if m > l _m (thus n < 1/l _m) then:
        (m I - A)^-1 > 0
        (I - n A)^-1 > 0

(i) max_i aⁱ1 ³ l _m ³ min_iaⁱ1 where aⁱ is the ith row of A. (i.e. maximum eigenvalue lies between the maximum and minimum of row sums of A).

Proofs of the various aspects of the Perron-Frobenius theorems (plus extensions) are given in Debreu and Herstein (1953), Morishima (1964), Murata (1977), Nikaido  (1960), Pasinetti (1975), Takayama (1974) and Kurz and Salvadori (1995).

Now we add the following definition from Hawkins and Simon (1949) and Georgescu-Roegen (1951):

Hawkins-Simon: a matrix A is "productive" or fulfills the "Hawkins-Simon conditions" if all the principal leading minors of A are positive.

and consequently another pair of theorems:

Theorem: Let A be an n ´ n matrix where a_ij £ 0 for i ¹ j, then there is an x ³ 0 such that Ax > 0 iff A fulfills the Hawkins-Simon condition.

Theorem: Let A be an n ´ n matrix where a_ij £ 0 for i ¹ j, then for any c ³ 0, there exists an x ³ 0 such that Ax = c iff A fulfills the Hawkins-Simon conditions.

Proofs of the above propositions can be found in Nikaido (1960; 1968: p.92).

Theorem: (Routh-Hurwitz) A necessary and sufficient condition that all the roots of the n-degree polynomial equation with real coefficients:

a_nl ⁿ + a_n-1l ^n-1 + .... + a₂l² + a₁l+ a₀ = 0

to have negative real parts is that all the principal leading minors of the following matrix are strictly positive:

	é	a1	a0	0	0	....	ù
	ê	a3	a2	a1	a0	....	ú
	ê	a5	a4	a3	a2	....	ú
	ê	....	....	....	....	....	ú
	ë	0	0	....		an	û

Note that the structure of the matrix for the Routh-Hurwitz conditions. The matrix is obtained as follows. The coefficients of the polynomial from a₁ to a_n are written out on the main diagonal. The columns consist in turn of coefficients with only odd or even subscripts, ith the coefficient a₀ included among the latter. All the other entries of the matrix corresponding to coefficients with subscripts greater than n or less than 0 are set equal to 0. 

From the Routh-Hurwitz conditions, it is immediately obvious that when we are coinsidering the characteristic equation of a 2 ´ 2 matrix A:

l ² - (trA)l + |A| = 0

that a necessary and sufficient condition for the real parts of all eigenvalues to be negative is that |A| > 0 and trA < 0.  A computationally simpler form of the Routh-Hurwitz conditions are the "Modified Routh-Hurwitz" conditions given in Murata (1977: p.92).

Back

Top

Selected References

Next