p .8 ) .   N i k a i d o⑦ p r e s e n t e d   an  i n t e r e s t i n g  p r o o f   which u t i l i z e d   t h e   Stiemke  t h e o r e m .   The p r o o f   by  N i k a i d o  i n   C , 〕u s e st h e  t h e o r y  o f  c l o s e d  convex c o n e ,  wh

‑269‑

A SIMPLE PROOF OF THE TUCKER  THEOREM 

Takao F u j i m o t o  

1 .   The Tucker theorem i n   l i n e a r   s y s t e m s   c a n   p r o d u c e  a l o t   o f  u s e f u l   c o r o l l a r i e s  and i s   i n d i s p e n s a b l e   i n   t h e  a n a l y s i s   o f  l i n e a r  economic m o d e l s .   The r e a d e r   may r e f e r  t o   Koopmans③ ,Howe② ,Nikaido勺 ， 9 〕e t c . Even i n   n o n l i n e a r  programming, t h e  Kuhn‑Tucker theorem① d e p e n d s  on  t h e   Minkowski‑Farkas  lemma,  which  i n   t u r n   i s   e a s i l y   d e r i v e d   from t h e   Tucker t h e o r e m .   The o r i g i n a l  p r o o f  due t o  Tucker (1 ゜ 〕 i sp u r e l y  a l g e b r a i c   and e l e m e n t a r y   ( h i s   THEOREM 1  i n   (1

p .8 ) .   N i k a i d o⑦ p r e s e n t e d   an  i n t e r e s t i n g  p r o o f   which u t i l i z e d   t h e   Stiemke  t h e o r e m .   The p r o o f   by  N i k a i d o  i n   C , 〕u s e st h e  t h e o r y  o f  c l o s e d  convex c o n e ,  which i s   e l e g a n t  b u t   a  l i t t l e   s o p h i s t i c a t e d .  

2 .   I n  t h e s e  p r o o f s ,   o p t i m i z a t i o n   d o e s   n o t   a p p e a r   e x p l i c i t l y .   Now i t   i s   w e l l   known t h a t   e x i s t e n c e   p r o b l e m s ,   s e p a r a t i o n  theorems and o p t i m i z a t i o n   p r o c e d u r e s  a r e  c l o s e l y  r e l a t e d  i n   some o f  economic t o p i c s .   We  may r e f e r  t o   a  s e r i e s  o f  p r o o f s  o f  t h e   e x i s t e n c e  o f   von Neumann growth e q u i l i b r i u m .   Another good example i s   t h a t  o f  N i k a i d o ③ ,whose method o f  p r o o f  seems  t o  be q u i t e  f r u i t f u l .   I n  Morishima‑Fujimoto ⑤ ,the Kuhn‑ Tucker theorem  i s   a p p l i e d  t o  a  m i n i m i z a t i o n  problem t o   p r o v e  a  n o n l i n e a r   e x t e n s i o n  o f  t h e   F r o b e n i u s  t h e o r e m ,  a v o i d i n g  t h e   f i x e d ‑ p o i n t  t h e o r e m s .  

* T h i s  n o t e  i s   a  r e v i s i o n  o f   my m i m e o .   ( 1 ． 〕

‑ 7 7  ‑

‑270‑

The p r o o f   i n   t h i s   n o t e   i s   performed  through  a s i m p l e   m i n i m i z a t i o n   problem and i s   s i m i l a r  t o   t h a t   u s e d   by Morishima  ( ( 的 p . 1 6 4 )   t o   p r o v e   t h e  Minkowski‑Farkas lemma. 

3 .   The Tucker theorem s t a t e s :  

THEOREM  Given any m 

n  r e a l  matrix A, t h e  f o l l o w i n g  two p r o b l e m s   ( i )   and  ( i i )   have  a t   l e a s t   o n e   p a i r   of s o l u t i o n s   s u c h   t h a t  

ぷ 十

p'A>Oand x;(p'A)i=O for a l l  i .   ( i )   f i n d  

s u c h  t h a t  Ax=O and x~o.

( i i )   find p s u c h  t h a t   p'A~O.

I n  t h e  t h e o r e m ,  x and p a r e  a r e a l  n‑column v e c t o r  and a  r e a l   m‑column  v e c t o r   r e s p e c t i v e l y ,   t h e   prime  i n d i c a t i n g   t r a n s p o s i t i o n .   S u b s c r i p t s   i ' s   a r e   u s e d  t o  s t a n d   f o r   t h e   i ‑ t h   e l e m e n t   o f   r e s p e c t i v e   v e c t o r s .   The i n e q u a l i t y   s i g n s   a r e   u s e d   i n   a u s u a l   s e n s e .   The above  p r e c i s e   r e s t a t e m e n t   o f   t h e   Tucker theorem i s   found i n  N i k a i d o⑦ p .   1 2 6 ,   C , 〕p .3 7 .  

4 .   Now h e r e  i s   a  s i m p l e  p r o o f :  

PROOF  I f   t h e   problem  ( i )   h a s  a s o l u t i o n   which i s   s t r i c t l y   p o s i t i v e ,   x>O, then p u t  P=O and we have t h e  d e s i r e d  r e s u l t .  

N e x t ,  s u p p o s e  t h a t  t h e   problem ( i )   h a s  no s o l u t i o n   s u c h  t h a t  x>O. 

e minimum number o f  z e r o   Then, t h e r e  i s   a  x  =（ふ，……云 n ) which h a s   t h

e l e m e n t ( s )  among t h e   s o l u t i o n s  o f   ( i ) .   Write t h i s   minimum number a s   r  a n d ,  w i t h o u t  t h e  l o s s   o f  g e n e r a l i t y ,  we s u p p o s e  

み＝

0 f o r   l~j~r, and 

0 f o r  

Of c o u r s e ,  r  may be e q u a l  t o  n ,   i n   which c a s e  t h e r e  e x i s t s  t h e  z e r o  s o l u t i o n   o n l y .   Let 

( 1 )   M=x'A'Ax. 

Now c o n s i d e r  t h e  f o l l o w i n g   m i n i m i z a t i o n  p r o b l e m .  

‑ 7 8  ‑

‑271‑

Problem:  Minimize M s u b j e c t  t o   Xj~O f o r  e a c h  j ,   and  ( 2 )

j=1.

j‑1 

Note t h a t  t h e  v a r i a b l e s  a r e  x/s and t h a t  t h e   summation ( 2 )   i n   t h e  con‑

s t r a i n t  r a n g e s  from  j  =  1  t o   r .  

S i n c e  t h e  above  problem i s   q u a d r a t i c ,   i t   h a s  a s o l u t i o n  v e c t o r  x * .   I t   c a n   be shown t h a t  t h e   minimum v a l u e  o f  M i s   p o s i t i v e ,   M*>O.  F o r ,  i f   i t   i s   z e r o ,   Ax*=  0 and we c a n   form a new v e c t o r   x 。＝云十x * , which s a t i s f i e s   Ax 。 =0, X 。 : 2 : : 0 and h a s   a l e s s   number o f  z e r o   e l e m e n t ( s )   than云 ， t h u s a  c o n t r a d i c t i o n .   Now we a p p l y  t h e  Lagrange  m u l t i p l i e r   theorem with non‑

n e g a t i v e  v a r i a b l e s .  

Form a  L a g r a n g i a n  f u n c t i o n ,   L=M‑1 （区巧ー 1 ) .

j=l 

At t h e  s o l u t i o n   p o i n t  x * ,   t h e r e   c a n   be  found t h e  m u l t i p l i e r   v a l u e

and we h a v e ,  

( 3 J   2x*'A'A‑

* e 。 こ 0 , ( 4 )  

where e 。 = ( 1 , . , 1 ,   0 , . , 0 ) ,   i . e .   t h e  f i r s t   r  e l e m e n t ( s )   a r e  u n i t y ,   o t h e r s  b e i n g   z e r o .   Using ( 1 )   and ( 2 ) ,   t h e  a b o v e  e q u a t i o n  ( 4 )  l e a d s  t o  

2M* —入＊＝ o.

Thus, we f i n d

i sp o s i t i v e .   Then, by p u t t i n g  p'= 2 x * ' A ' ,  i t   f o l l o w s  from  ( 3 )   t h a t   p'A~O, where t h e   f i r s t   r  e l e m e n t s   a r e   p o s i t i v e .   T h e r e f o r e ,   we  o b t a i n 云 '+P'A>O. Moreover,  s i n c e   Ax=O, t h e   v e c t o r   x* ＋云 i s a g a i n   a  s o l u t i o n  whose l a s t  n‑r e l e m e n t s  a r e  s t r i c t l y  p o s i t i v e .   S u p p o s i n g  x* i s   a l r e a d y   s u c h  a  s o l u t i o n ,   then from ( 3 )   and ( 4 ) ,

A);=Of o r  

Thus, 

ふ（元

'A);=Of o r  a l l   i .   QED. 

‑ 7 9  ‑

‑272‑

REFERENCES 

[  1  ] .   T .  Fujimoto,'An A l t e r n a t i v e   P r o o f  o f   t h e   Tucker Theorem,'mimeo.  ( 1 9 7 5 )   [  2 ] .   C .   W. Howe,'An A l t e r n a t i v e   P r o o f  o f  t h e   E x i s t e n c e  o f   G e n e r a l  E q u i l i b r i u m  

i n   a  Von Neumann Model,'Econometrica ( 1 9 6 0 )  

[  3 ] .   T .  

Koopmans ( e d . ) ,   A c t i v i t y  A n a l y s i s  of P r o d u c t i o n  and A l l o c a t i o n ,   ( J o h n   Wiley & S o n s ,   1 9 5 1 )  

[  4  ] .   H .  W. Kuhn and A .  W. Tucker,'Nonlinear Programming,'in J .   Neyman ( e d . ) ,   P r o c e e d i n g s   of t h e   S e c o n d  B e r k e l e y   Symposium o n   Mathematical  S t a t i s t i c s  and  P r o b a b i l i t y  ( B e r k e l e y ,  1 9 5 0 )  

[  5 ] .   M. M o r i s h i m a ,  Theory of Economic Growth, ( O x f o r d ,  1 9 6 9 )  

[  6 ] .   M. Morishima and  T .   Fujimoto,'Frobenius  Theorem,  I t s   Solow‑Samuelson  E x t e n s i o n  and t h e  Kuhn‑Tucker Theorem,'Journal of Math. E c o n .   ( 1 9 7 4 )   [  7 ] .   H .  N i k a i d o ,   Keizai n o  tame n o  S e n k e i ‑ s u g a k u   ( L i n e a r  Mathematics for Econo‑

m i s t s ) ,   i n  J a p a n e s e ,   ( B a i f u k a n ,  1 9 6 1 )  

[  8 ] .   H .  N i k a i d o , ' G e n e r a l i z e d  Gross S u b s t i t u t a b i l i t y  and E x t r e m i z a t i o n , ' i n  M. Dre‑

s h e r ,   L .   S .   S h a p l e y   and  A .   W. Tucker  ( e d .   s ) ,   Advances  i n   Game T h e o r y ,   ( P r i n c e t o n ,   1 9 6 4 )  

[  9 ] .   H .  N i k a i d o ,  Convex  S t r u c t u r e s  and Economic T h e o r y ,   (Academic P r e s s ,   1 9 6 8 )   [ 1 0 ] .   A. W. Tucker,'Dual Systems o f  Homogeneous L i n e a r  R e l a t i o n s , ' i n  H .  W. Kuhn 

and A .  W. Tucker ( e d .   s ) ,   L i n e a r  I n e q u a l i t i e s  and R e l a t e d  S y s t e m s ,   ( P r i n c e t o n ,   1 9 5 6 )  

‑ 8 0  ‑