\SMUZJ)

NATIONAL BUREAU OF STANDARDS REPORT

11*73

A THEOREM OH CONVEX CONES WITH APPLICATIONS

TO LINEAR ^EQUALITIES

Jerry W, Gaddum

National Bureau of Standards, Los Angeles, California

U. S. DEPARTMENT OF COMMERCE

NATIONAL BUREAU OF STANDARDS
U. S. DEPARTMENT OF COMMERCE

Diaries Sawyer, Secretary

NATIONAL BUREAU OF STANDARDS

A. V. As tin, Acting Director

THE NATIONAL BUREAU OF STANDARDS

The scope of activities of the National Bureau of Standards is suggested in the following listing of the divisions and sections engaged in technical work. In general, each section is en- gaged in specialised research, development, and engineering in the field indicated by its

title. A brief description of the activities, and of the resultant reports and publications,

appears on the inside of the back cover of this report.

|. ELECTRICITY. Resistance Measurements. Inductance and Capacitance. Electrical Instruments. Magnetic Measurements. Electrochemistry

2. OPTICS AND METROLOGY. Photometry and Colorimetry. Optical Instruments. Photographic

Technology. Length. Gage.

3. HEAT AND POWER. Temperature Measurements. Thermodynamics. Cryogenics. Engines and

Lubrication. Engine Fbeis.

*. atomic and radiation physics. Spectroscopy. Radi ome try. Mass Spectrometry, physical Electronics. Electron Physics. Atomic Physics. Neutron Measurements. Nuclear Physics. Radioactivity. X-Rays. Betatron. Nucleonic Instrumentation. Radiological Equipment. Atomic Energy Commission Instruments Branch.

5. CHEMISTRY. Organic Coatings. Surface Chemistry. Organic Chemistry. Analytical Chemistry. Inorganic Chemistry. Electrodeposition. Gas Chemistry. Physical Chemistry. Thermochemistry. Spectrochemistry. Pure Substances.

6. MECHANICS. Sound. Mechanical Instruments. Aerodynamics. Engineering Mechanics. Hydraulics. Mass. "Capacity, Density, and Fluid Meters.

7. ORGANIC AND FIBROUS MATERIALS. Rubber. Textiles. Paper. Leather. Testing and

Specifications. Organic Plastics. Dental Research.

8. METALLURGY. Thermal Metallurgy. Chemical Metallurgy. Mechanical Metallurgy . Corrosion.

9. MINERAL PRODUCTS. Porcelain and Pottery. Glass. Refractories. Enameled Metals. Building Stone. Concreting Materials. Constitution and Microstructure. Chemistry ' of Mineral

Products.

10. BUILDING TECHNOLOGY. Structural Engineering. Fire Protection. Heating and Air Conditioning. Exterior and Interior Coverings. Codes and Specifications.

11. APPLIED MATHEMATICS. Numerical Analysis. Computation. Statistical Engineering. Ma- chine Development.

12. ELECTRONICS. Engineering Electronics. Electron Tubes. Electronic Computers. Electronic Instrumentation

13. ORDNANCE DEVELOPMENT. Mechanical Research and Development. Electromechanical

Fuzes. Technical Services. Missile Fuzing Research. Missile Fuzing Development. Projectile Fuzes. Ordnance Components. Ordnance Tests. Ordnance Research.

14. RADIO PROPAGATION. Upper Atmosphere Research. Ionospheric Research. Regular Propagation Services. Frequency Utilization Research. Tropospheric Propagation Research. High

Frequency Standards. Microwave Standards.

15* MISSILE DEVELOPMENT. Missile Engineering. Missile Dynamics. Missile Intelligence.

Missile Instrumentation. Technical Services. Combustion.
NBS PROJECT

1101-21-5102

February 11, 1952

NBS REPORT

1U73

A THEOREM ON CONVEX CONES WITH APPLICATIONS

TO LINEAR INEQUALITIES*

Jerry W.® Gaddum

National Bureau of Standards, Los Angeles, California.

PREPRINT

'H -X” , The preparation of this paper was sponsored (in part) by the Office

of Scientific- Research, USAF<*

This report is issued for

in any fora, either in whol

fro* the Office of the Dire

Approved for public release by the

Director of the National Institute of

Standards and Technology (NIST) on October 9, 2015

reprinting, or reproduction

sion in writing is obteined

ngton 25, D. C.
. . • . t - 0 i
UBS No* lk73

2-11-52

PREPRINT COPY

A Theorem on Convex Cones with Applications

_y/_ to Linear Inequalities

Jeriy W„ Gaddum

National Bureau of Standards, Los Angeles, California

1. INTRODUCTION

This note is concerned with the convex cone associated with

the two systems of linear inequalities

n * (1) 2 a.. . x. « 0, i » 1, 2, ••• m, and

0-1 0 0

n

( 2 ) 2 a. . x = ^ 0, i » 1, 2, 0<,e

, m, where the symbol

demands that the inequality ( > ) hold for at least one value of i,

For brevity these systems will be written (l) Ax 0 and (2) Ax ^ 0.

Interpreting * (a. nd a. ) as a vector a. in E s with initial ^ il* J in i r/

point at the origin, we denote by A the convex cone generated by

these m vectors and by A'' the polar cone, the vectors of which give

the solutions of (l) e A cone will be considered null if it contains

only (0, 0, •••, 0).

The purpose of this paper is to show that in general A ® A ^ 0

and to characterize the cases in which A and A do not intersect ? Some applications are then made to obtain theorems on the existence

-XThe preparation of this paper was sponsored (in part-) by the Office

of Scientific Research, USAF,
.

.

'

.
- 2 -

of, and methods of obtaining, solutions of (l) and (2) c He THE MAIN THEOREM

Before proving the main theorem, it should be remarked that

the proof given does not require that the cone A be generated by

finitely many vectors but the applications to be made do require

this. The theorem, of which a special case has been stated in

[2]^, can be formulated as follows

Theorem 2.1. If A" is no nr- null and if some vector of A is

not perpendicular to all the vectors of A then A * A" ^ 0.

Proof . Let x be a vector of A which is not perpendicular to

all the vectors of A". If x is not in A' (otherwise the theorem

holds immediately) let y be that vector of A', of unit length,

closest to x. In other words, among the unit vectors of A

',

y makes the inner product x • y a maximum. In the hyperplane

orthogonal to y let u be the unit vector farthest from x, that is,

minimizing x • u. Now u is a vector of A. This follows since it is a vector

of the polar cone of A and since (A")

- ' - Ac To see that u is in

(A")" we remark that if A" contained a vector z making an obtuse

angle with u, the plane containing y and z would contain a unit

vector of A.'' closer to x than y.

Letting % - , the vector y - %x is orthogonal to js since

y is a unit vector. Among the unit vectors orthogonal to y, u

^Numbers in brackets refer to the bibliography*

>

minimizes x « u and hence maximizes y - Xx ° Thus y - ^x has the

same direction as 11

, and y - Xx ~ ku^ k > 0„

Then y ~ Xx + ku^ X an<^ k both positive^ and y is a vector in

A A* A ° A e

If A is not contained in an E _ * the conditions of the theorem

n-1*

are satisfied upless A

” is null. If A is contained irreducibly in

an E , r < n9 and A ® A' s then A is equal to the E * since no

vector of A

' lies in the E <> Thus we can characterize those cones

r with A ° A” - 0 as follows?

Theorem 2<,2 0 A • A" - 0 if and . only if A is an E^ and A'' an

orthogonal E^ ®

IIIo SOME EXISTENCE THEOREMS

In this section the foregoing discussion is applied to obtain

theorems on the existence of solutions for a system of linearinequalities. A vector y is called positive if y^ > 0 for each i,

non-negative if y^

s 0 for each i and y^ > 0 for some i.

Theorem 3d. The system (2) has a solution if and only if

A 0 AT 4 0 • The proof being immediate from Theorem 2.2, we state the same

result algebraically.

Corollaxy % If (2) has a solution it has one of the form

x s A

? y , where y is non-negative and A

8 is the transpose of the

matrix A„

Theorem 3.2. In order that- (2) have a solution, it is necessary

and sufficient that the system AA*y - 0 have a non-negative solution.
. • " " ' *;
Proof : Firsts if AA 5 y

~ 0 has any solution at all, the relaiion

x s A !y gives a solution of Ax - 0® On the other hand, if Ax - 0

has a solution, the corollary to Theorem 3d states that it has

one of the form x * A 8 y, y non-negative, and this y is a solution

of AA 9 y - 0 o

It should be observed that this theorem is a strengthening

of the result, in [l], that Ax ~ 0 and AA 8 y ^ 0 are either both

consistent or both inconsistent 0 Corollary ; If B is a symmetric positive semi-definite matrix^

By - 0 has a solution if and only if it has a non-negative one . Corollary t A sufficient condition that (l) have a solution

' is that AA’y - 0 have a (non-negative) solution* Corollary ; If the rank of A is n, a necessary condition that

(l) have a non-trivial solution is that AA 8y « 0 have a (non-ne|

solution^

In [3] a necessary and sufficient condition is given that a

system of type (2) be solvable . Using Theorem 2 of [3] we can

state the following theorem*

Theorem 3*3» AA *y ~ 0 (and hence ( 2 )

)

has a solution if and

only if AA 8 y ~ 0 has no positive solution* In [1|] a method is given for determining whether or not a

system of homogeneous linear equations has a positive solution.

In the form given, however, the method does not seem feasible for

purposes of computation*

An obvious necessary condition that AA 8 y = 0 have a positive

solution is that for ary collection of rows of AA \ the m column

-5-

sums be all zero or have a pair of terms of opposite sign. Hence

a sufficient condition that AA ey ~ 0 (and hence (2)) have a solution

is that for some collection of rows of AA% the m column sums form

a non-negative set*

Still another form can be given to the problem of determining

whether or not AA 8y - 0 is solvable c Let us write AA 5 ~ B * (b. .)

and denote the rank of B by r, We can suppose that the r-th order

principal minor in the upper left-hand corner^ is non-singular

and^ for the purpose of solving By s 0, we can assume its determinant positive* For 1 ^ j ^ r and r + 1 ~ k ^ m9 let denote

the negative of the determinant of the matrix obtained from R by

substituting the first r elements of the k-th column of B for the

j-th column of R« If we assign values arbitrarily to J.r ^ 9 •••, y.^

and solve By * 0 for y ,

• ® ® s y^ we obtain^ for j - ls 29

• • % r9 y. “ [/?. , y ^ . y ]• Thus the problem reduces

J

j R |

1 jr+1 r+1 r jm ^ m

^

to that of finding positive solutions of the sys terns

fl> m „ y + + k, y ) 0 p lr+1 ^r+l , lm

o

^ rr+1 ^r+1

+ ^ rm 4> m ^ *

In Theorem p* 50^ of [%] 9 a criterion for the existence

of positive solutions of this system is given*

IV* COMPUTATION OF SOLUTIONS

Theorem 2*1 suggests a method for computing a solution of a

system of inequalities^ assuming a solution exists* We begin by

normalizing the rows of the matrix k3 that is^ by making
' . . I . ' • I " ' " I * .
-6»

aj. 2

2 a; , = 1 for each i. We then siirply generate a set of unit

j®l ^ vectors dense in the set of unit vectors of A, and hence come

arbitrarily close to some vector of A * A% If A A* / 0. This,

can be done by adjoining to the vectors corresponding to the rows

of A the mid-vector of each pair* If no solutions are obtained at

the first step, continue the process on the larger set of vectors*

The normalized midvector of the vectors a and b has for its k-th

component (a^ + b^)/y2(l+a«b)

_

'«, The computation of one midpoint

presents no problem but the number of such confutations becomes

very large as we repeat the process* It would therefore be of

considerable value to know how to find only essential midpoints*

February lU, 1952
-

*
-7-

BIBLIOGRAPHY

[1] S 0 Agmon, The Relaxation Method for Linear Inequalities

Prepublication Copy® National Bureau of Standards^

Los Angeles, California©

[2] Lo Mo Blumenthal, Metric Methods in Linear Inequalities©

Duke Mathematical Journal, vol© 15 (I9 I4

. 8 ) pp c 955“966©

[3] Lo Lo Dines, Note on Certain Associated Systems of Linear

Equalities and Inequalities* 'Annals of Mathematics,

Second Series, vole 28(1926-27) pp® Ul-U2©

[U] L, Lo Dines, On Positive Solutions of a System of Linear

Equations o Annals of Mathematics, Second Series, volo 28

(1926-27) pp ® 386-392©

[5] To So Motzkin, Beitrage Zur Theorie der Linearen Ungleichunger©

Jerusalem, 1936 e