]. Korean Math. Soc. 26(1989). No. 2. pp.271-281
MINIMUM PERMANENT ON CLASSES OF NONNEGATIVE MATRICES
SI JOO KIM
1. Introduction
Let m and n be positive integers, and let R=(rh ..., rm) and S=
(Sh ... , sn) be nonnegative integral vectors with rl+ .•. +rm=sl+ ••• +Sn.
We denote by OR,S the set of all nonnegative mXn matrices A=[aij]
satisfying
"
.I:aij=ri
j=1
for i=l, ...,m;
m
"fraij=Sj for j=l, ...,n.
Thus a nonnegative matrix belongs to OR,S provided its row sum vector is R and its column sum vector is S. The class OR,Sis, of necessary, nonempty.
The permanent per(A) of an mXn(ms.n) matrix A= [aij] is defined by
m
per(A)= .I:aioei)
;=1
where the summation extends over all one-to-one functions from {I, ..., m} to {I, ..., n}. A well-known case of the permanent function occurs when m=n and R=S=(1, ...,1). In this case, QR,S=Qn, the polytope of all nXn doubly stochastic matrices, and the minimum permanent value is n! / nn as a result of the recently proved van der Waerden coniecture [6J:
The purpose of the present paper is to investigate properties of matrices with minimum permanent on OR,S and to determine the minimizing matrices on QR,S and their permanent values for some special Rand S.
Two nXn matrices A= [aiJ and B=[bij] are said to have the same
Received February 14, 1989.
- 271-
'02 Si Joo Kim
zero pattern if aij=O implies bij=O, and vice versa. For p,qE {l, 2, ..., n}, let Epq= [eij]nXn be defined by
e ..=[l, if (i, j)= (p,q)
'J 0, otherwise
2. Genaral Case
Let R= (rh ..., rn) and S= (Sl> "', sn) be positive integral vectors such that tri=tsi and rlS;; .••S;;rn,Sl~...~Sn'Then OR,S is nonempty
;=1 i=1
and a convex hull which contains no more than (n-1)2+1 vertices called extremal matrices [4J. Let
MR,s={AEOR,slper(A) S;;per(X) ,VXEOR,s}.
Then MR,si=t/J. If rl+r2+ ...+ri+l~sl+S2+... +Si' i=l, 2, ..., n-1, then min per(X)>0.
XEJ1R.$
LEMMA 2. 1. Let A= [aijJ= [Ah ..., An] E MR,S. If SI =S2 and the vectors Al and Az have the same zero pattern, then
(1) there exists a constant c such that per (A (i11) )-per (A (i\2) )=c for all i with aiji=O.
(2) per(A) --per [Al+A22 ' A 1+A2 A2 ,3, ...,A]n '
Similar statements hold for rows.
Proof. For i,jE{l,2, ...,n}, let Pij=per (A(i\j)). Without loss of generality, we may assume that aij>O for i=l, ..., k, j=1,2 and aij=O for i=k+1, ...,n, j=1,2.
(1) If k:::;1, there's nothing to prove. So we may assume that k~
2. Let Pn-P12=C. Let us take any i with 2S;;i:::;k. For a real number
E,let A(E)=A+E(En-E12-Eil+Ei2). Then A(E)EDR,s for IEI:::;min {an,alZ, ail> aiZ} and per (A (E) )=per(A)+ (Pn-Pt2-Pil+Piz)f+O(f2).
Thus Pn-PI2-Pil+Pi2=0, i.e., PU-Pi2=Pn-P!2=C.
(2) By (1), we have ailPi2 =ail (Pil-C) andaiZPil =ai2 (P."2+c) for all i=l, ..., n, since Al and A2 have the same zero pattern. Thus per [ A1
t A2 , A1tA2.' A3, ..., An]= ~ (per[Al> Ab A3, ..., AnJ+per[Al>A z, 1 "
A:b ..., An]+per[A2, AI> A3, ..., An]+per[A2, A 2, A3, ... , An]=4"~auPi2
n 1 n n 1 n +2per(A) ~ai2Pil = 4(t;iail(Pil- C) +2per(A) + ~ai2(Pi2+C)= 4(t;i
11 11 n 1
ailPil +2per(A) + ~ai2Pi2+ (~lai2-i~ail)c)=4 (per(A) +2per(A) +per (A» =per (A).
Let's call the argument in the proof of (1) the 4-cycle argument.
For i,j, s,tE {I, ...,n} with i<j, s<t, let's write L1A(i, j : s, t) = per (A (iIs) )-per (A (iIt) -per (A(jIs» +per (A(jIt». It there is no risk of ambiguity, we write L1(i,j : s, t) instead of L1A(i,j : s, t).
THEOREM 2.2. Suppose that Sl= ... =Sk for some ks;,n. Let A=[Ah
..., A,,]E M R,S. If Ah ••• ,Ak have the same zero pattern, then Per(A) -p- er[AI+ ... +Akk ' ..., A1+ ... +Ak Ak , k + h ••. ,A]" .
A similar statement holds for rows.
Proof. The case k=2 is done in lemma 2.1, (2) and the assertion may be written as per(A (J2ffiI,,-2) ) = per (A). By repeating the averaging process, we have A (MkffiI,,-k)E {JR, S and per (A (Mkffi I,,-k» =per(A), where M k= (J2ffih-2) (IlffiJ2ffih-3) ... (h-2ffiJ2 ).
Thus A(MkffiI,,-k)tE{JR,S and per(A (MkffiI,,_k)t) =per(A) for all
t=l, 2, .... Since lim Mkt=h, we have per (A) =lim per (A (MkffiI,,_k)t)
t_~ t-=
=per(A(JkffiI,,-k)' But
A(JkW ,,-kCf'I ) - [ A1+···+Ak- k ' "', A1+···+Ak Ak , k + h ••• ,A]" .
3. The case R=(1, t, ..., t), S=(t, ..., t,1), t?:.n
From now on, in the sequel, let's restrict ourselves to the particular case of {JR.S where R=(1,t, ..., t) and s= (t, ...t,1) are n-tuples, t?:. n. Let
it IS
When n=2,
o
"
1"
1
t-1 1
t-1,, ,
o "t-1 'I Since U"E{JR,S' we know that min per(X) s;,l.
XED R.S
easily seen that
274 Si 100 Kim
min per (X) =[ ~
XeDR,S 1
if t=2 if t~3
and
if t=2
if t~3.
41 3
4 43
45 MR,s=
(t~l ~ J
we have the following conjecture.
For n~3,
CoNJECTURE 1. Let n~3. Then, for any XEQR.S' per (X) ~1 with equality if and only if X=Un upto permutations of last n-1 rows and first n-1 columns.
THEOREM 3.1. Let n~3 and AEMR,s. Then
(1) If alt>O and per(A(l!t» >Per(A) , then there exists s( =l=t) such that als>O and per(A(lls»<per(A). If atn>O and per(A(tln»
>per(A) , then there exists s(=I=t) such that asn>O and Per(A(sln»
<per(A).
(2) If per(A(1In)<2per(A) and aln>O, then A(lln) is not a positive matrix
(3) IfA(lln»O, then neither (an, ...al,n-l) nor (a2n, ...,ann) is positive
(4) A is not positive
"
Proof. (1) The first assertion follows from the fact that L;alj=l
j=l
"
and L;alj per(A(l!i»=per(A). Similarly, the second one does.
j=l
(2) Suppose that per(A(1In»>2per(A), aln>O and A(lln»O.
Then, by (1), there exist s (=1=n) , t (=1=1) such that als>0, atn>O, per(A(lls»<per(A) and per(A(tln»<per(A). So, LI(l, t : s, n)<
2per(A)-2per(A)=0. Since A(lln»O, ats>O. Thus the 4-cycle argument implies that Ae;;MR• S' This is a contradiction.
(3) Suppose that A(11n)>0 and (a2n' ..., ann)>0. Without loss of generality, we may assume that an, ...,au=l=O and al.k+l= ... =al.n-l
=0, where O:S:k:S:n-l. Notice that the columns AI. "',Ak are of the
same zero pattern, the columns Ak+h " ' ,An-I are of same zero pattern and the rows A2, "', An are of the same pattern. So by theorem 2.2, we may assume that
a... a 0... 0 aIn
A= C •••c d ...d b
C •••c d ... d b
' - - - v - - - ' ' - - - v - - - '
k n-k-1
where a>O, c= (t-a) / (n-1) >1 and d=t/ (n-1) >1. If k=O, then aIn=l and b=O. Hence per(A)=per(A(1In))=(t/(n-1))'.-l(n-1)!
~2per(A), which is impossible. Therefore k~1. So an>O. By (1), per(A(l!l))<per(A) and per(A(nln))<per(A). But A(lln)=
(n-1)Jn- I+B, whereIn- I is (n-1) X (n-1) matrix all of whose entries are 1/(n-1) and B>O. Thus per(A(1In))>(n-1)!~2~2per(A).
Therefore it must be that aIn=O by (2). So a=l/k and b=l/ (n-1).
Thus
[
c ...c Id ... d Ib ) [ 1. ..1
per (A) =kaXper : : : : : >per : :
c ...c d ...d b 1...1
~ ~
k-1 n-k-1
This is a contradiction.
(4) It follows immediately from (3).
11=(n-2)!~1.
THEOREM 3.2. Let n~3 and AEMR,s. If A is partly decomposable,
then A(11 n) is not Positive
Proof. Let A= [au] be partly decomposable with AEMR,s. Suppose that A (11 n) >0. Since A is partly decomposable, alj= 1 or ain= 1 for some i, j, 15:, i, j 5:, n. If i=1 or j=n, then per (A) =tn-Iper Un-I) = tn- l (n-1)1/(n-1)n-I=(t/(n-1))n-l(n-1)1>1, which is impossible.
For aIj=l, j:f=n, we may assume that al1=l, a2n:f=0, ..., ak+l,n:f=O and ak+2,n= ... =ann=0, where 15:,k5:,n-2, by theorem 3.1, (3). Then, by theorem 2. 2,
276
per(A)=
Si Joo Kim
1 \ 0...0 I0
% X •••x b.
z x x b
w y .••y. 0.
w y .••y 0
k
n-k-I
=(n-2)!X1-1y,,-1-1 where x,y,z,w,b>O and
t(k-I) <' < . (t-b t)
k(n-2) x mm n-2'k . If k=1, o<x< (t-I) / (n-2) and
. t-I
(t-x )"-2 ( t - -2 )"-2
per (A)= (n-2)! n-2. >(n-2)!n~-; .
= (n-2)' (t(n-3). (n-2)2+1 )"-2>1- ,
which is impossible. If1<k<n-l, (n24),then ~~:=g <x<~ ; and
per (A) (n-2)! x1-1(t-kx)"-l-1> (n-2)! ( t-b )l-l (n-k-I)" l 1 (n-k-1)" l 1 n-2 (t k(t-b) ),,-l-l> (n-2)! (t(n-k-2)+1),,-l-l
n-2 (n-k-I)" l 1 n-2
>( )I( t(n-k-2)+I ) ,,-k-1 , h'h" 'bl n-2 . (n-2) (n-k-I) 2:1, ,w 1C IS 1mpoSS1 e.
The case ai,,=1, i*1 is impossible by a similar process above.
THEOREM 3.3. For n=3, the conjecture is true
Proof. Let n=3 and A=[aij]EMR,s, where R=(1,t, t) and S=
(t, t,1), t23. Then A(II3) is not positive. For, suppose that A(II 3) >0. Then, by theorem 3. 1, (3), neither (an, a12) nor (a23, a33) is zero. By permuting rows A2 and A3, columns Al and A 2(ifnecessary), we may assume that a12=a23=0 and A may be written as
a 0 I-a
A= x t-x 0
t-x-a x a
Then per(A(II3))=x2+ (t-x) (t-x-a) 2x2+ (t-x) (t-x-l)=2x2 -(2t-I)x+t(t-I) 2 (4t2-4t-I)/8223/8>2per(A). So, by theorem
3. 1, (2), it must be that 1-a=a13=0, i. e., a=1. Hence a31 =t-1 -x>O. Thus per (A) =t-x>l which is impossible. ThereforeA(113) is not positive. Now without loss of generality, we may assume that a31 = 0. Let's rewrite A as
P b a
A= x
° y
Then x, Y2t-1 and a, c:S:1. If either a or c is 0, then it is easily checked that per(A) 2t. Hence a, c>O and x, y<t. Suppose that A (311»0. Then ..:::1(1,2: 2, 3) = (a-x) (y-c) ,*0, since a:S:1<t-1:S:x and c:S:1<t-1:S:y Thus the 4-cycle argument implies Afl:.MR,s which is a contradiction. So it must be that A(3/1) is not positive, i. e. , at least one of a12, a13, a22, a23 is 0. Next we claim that a22 = b'*0.
For, suppose, on the contrary, that b=O. Then q=a, P=c and
Let
a
A= x
°
c
°
y
r a c
c a r
A'= y ° c
° x a
Then A'E MR ,S and has the same zero pattern as A. Let A(t) =
(l-t)A+tA'. Then there exists E>O such that A(t) EQR,S for all tE [-E,l+EJ. Letf(t)=per(A(t)). Then, since A,A'EMR,s, we have f' (0) =f' (1) =0 and feD) = (1). Thus f(t) is constant function, since it is a polynomial of degree 3, i. e., jet) =f(O) , VtE [-E,1+E]. And especially per(A) =per( ~ (A+A')) and hence ~ (A+A') EMR,s. Let B= ~ (A+A'). Then B may be written as
d d r
B=[b;j]= z ° d
° z d
where d=(a+c)/2 and z=(x+y)/2. Now, ..:::1(1,2: 1,3)=dz+dz- z2-d2-rz:S: (z-d)2<0, since z2t-l>12d. Hence it must be that b13=r=O. For, if not, the 4-cycle argument will yield a matrix C in QR,S with per (C) <per (B) since bl l=b23=d>0. Hence d= ~ and
278 Si Joo Kim
%=t- ~. Thus per (B) = (2t-l)/4. So we have per(A)=per(B)=
(2t-l)/4>I~per(A),a contradiction! Hence a22:;l=O. Therefore, at least one of a12, a13, a23 is o. We want to show that a12a23=O. For, suppose not. Then a12:;l=O and a23:;l=O. Thus aI3=0. By the same argument above, we have the following matrix
B=[bii]=[~ I~d 1~d ] EaR•S
o % d
such that per(A)=per(B). B may be rewritten as
[
I t-% %-t+1 °
B=B(%)= % 2t-2%.-1 %-t+1
o % t-%
Since aI2;i::O, we must have t-1<%~t- ~ and fez) =per(B(z))
= (t-z) {(2t-2z-I)(i-z) +z(z-i+)} +%«z-t+I) (t-z). Since
f'(%) =-2{6z2+ (3-10t)z+4t2-2t}~O, t~I<z~t-~, per(B) fez)
>f(t-l) =1, which is impossible. Hence either al2 or a23 is 0.
Without loss of generality, we may assume that aI2=0. So A is written as
A= [a'j]=[ ~ : ~c: .
Notice that t-I~x,y<t and O<a,c~1 per(II3)=xy~(t-l)2>per
(A). Thus by theorem 3. 1, (1), per(A(111) ) <per CA):s;;1 and per (A(213)) =ay<t. So, Lt(1, 2 : 1, 3) <1+t- (t-l) 2_per (A (2/1)):s;;- t(t-3):s;;o. Hence the 4-cycle argument implies either a13=0 or a23=
0. If aI3=0, then A is written as
A=[aii]=[ t~1 t~y y-~+I, t-l~y~t.
. 0 Y t-y
And per(A)=(t-y)2+ y (y-t+1)=2y2-(3t-l)y+t2 takes the mlm- mum value 1 uniquely at y=t-1. Thus A=U3. If a23=O, A is written as
A=[a'j]= [
t-x x
o t-x°
x
x-t+l ]
° ,t-1:S;;x:S;;t.
t-x
And per(A)= (t-x)3+ x 2(x-t+1) = (2t-1)x2-3t2x+t3 takes the minimum value 1 uniquely at x=t-l. Thus A= U3.
THEOREM 3.4. Let AEMR,s be partly decomposable 4X4 matrix.
Then A=U4 upto permutations of last n-1 rows and first n-1 columns.
Proof. Let A= [aij]E M R,s be a partly decomposable 4X4 matrix.
If aij=t for some 2::;;i:sA, 1::;;j::;;3, without loss of generality, we may assume that a41 =t. Hence an =a21 =a31 =a42=a43=a44=0. By Theorem 3.3, per(A) =tXper(A(4!1» :::::tX1>1, which is impossible.
Thus we may assume that O::;;aij<t, 2::;;i::;;4, 1::;;j::;;3. Since A is partly decomposable, it is sufficient to consider only the five cases (1) a14=1 (2) A(1,211,2)=0 (3) A(1,213,4)=0 (4) A(3,411,2)=Oand (5) an=1. First of all, we claim that the cases (1), (2) and (3) do not occur.
case(l) a14=1: Then per (A) =per(A(1!4» :::::t3X31/33>1, which is impossible.
case (2) A(1,2 : 1, 2) =0 : Let
a b c d
e f g h
A= i J 0 0 EMR,s·
k l O O
Since (i,j,k, l)>0, by the averaging process,
a b c d
e f g h
per(A) =per
x y 0 0
x y 0 0
where x, y>O. Suppose that (c, d, g,h)>0. Then L1 (1, 2 : 3, 4) = 2(h-g-d+c)xy=0. Hence h+c=g+d and 4:::::2 (h+c) =g+c+d+h=
+1::::: 5, which is impossible. Thus we may assume that (c,g,h)>0 and d=O. Since L1(1, 2 : 2,3) =2xy(d-h) *0, a=O or e=O. If a=O, suppose that (e,j) >0. Then L1 (2,3 : 1,2) =c(x- y) and hence x= y, which implies e=f=O, a contradiction! Hence e=O or f=O. In the both cases, per (A) =t2/2>1, which is impossible. If e=O and a>O, then b=O. Since a=t-2x>0 and f=2x-t:::::0, t/2::;;x<t/2, a contr- adiction! By the same argument above, we can have contradictions in case (3) and (4).
case(5) an=l: Then a12=a13=a14=0. By theorem 3.2, we may
280 Si Joo Kim
per(A)=per
l
assume that an=0 or a23=0. First, let an=0 and
A=
~ ~ ~
f)EM~s.
If a=O or e=O, then, by theorem 3.3, PAQ= U4 for some permut- ation matrices P, Q. It is easy to prove that a=O or e=O. Hence, without loss of generality, it is sufficient to consider only the following three cases (a) i=O (f3) c=O and (r) d=O.
case(a) i=O. Suppose that (c, d, g, h)>0. Then
1 0 0 0
t-1 t 1
-2- 2 x 2-x
t-1 t 1
2 2 x 2-x
o 0 t-2x 2x
=t(4x2- (t+ 1)x+t/2) >t/2>1, 0<x<l/2.
Without loss of generality, we may assume that either c or d is zero.
In the case of c=O, d>O. Ifh>O, b f. But LI(3,4 : 3,4) =0 implies k+g=j+d+h. Hence j=(3t-1)/4 and k=t-j=(t+1)/4>1 which is impossible. Thus h=O. Since LI(2,3 : 1,2) =0, g=t/ (t+1). But per(A)= (b+f)g2=t(t/ (t+1))2>1, a contradiction! By the similar method, the case d= 0 will be done.
case (f3) c= 0: Let
1 0 0 0
a b 0 .d
A= e f g h R , S ·EM
o i j k
We may assume that (b, d,g,i,j) >0. Otherwise we can derive a contradiction from the cases (2) , (4) and (a). Suppose that (h,!, k»
O. Since LI(3,4 : 2,3) =0, j=g or b=d If j=g, then b=f+i=t/2and per(A) =t2/4>1. If b=d, then A can be written as
1 0 0 0
t-2d d 0 d
A= 2d-1 x t-y y-x-2d+1
o t-d-x y d+x-y
Then (2t-1)/4::;:y::;:(2t+1)/4. Since .,1(2,3; 1,2)=LI(2,3; 1,4)=0,
y=(2t-1+-v!(28t2-4t+1»/12>(2t+1)1/4, a contradiction! Hence at least one of f, hand k is zero. If f=O, then h=O and hence k=O are easily checked. Then per(A)=gi=g2>1. If h=O, then we may assume that (b, dJ, g, i,j)>0. Then per (A)=bkg+ gid+ fjd=d(bj+
gi+fj) =d((t-i)j+gi) =d(tj+ (g- j)i) =d(t2(1-d)+(2td-t) (td+d -1» =d (2t( ((t+ 1)d2-t(2t+3)d+t(t+1» =dt(2(t+ 1)d2- (2t+3) d +(t+1»>1 where 1/(t+1)sdsl. If k=O, then we may assume that (b, dJ, g, i,j,h)>0. Since A(2,3: 1,2)=A(3,4 : 2,3) =0, d=h and i=j=g=t/2. Thus per(A) =t2/4>1, which is impossible. Case (r) will be done by the same argument above. Thus we have the result.
REMARK. The conjecture 1 is equivalent to the following.
CONJECTURE 2. Let S71={X=[xij]EQ711 t-1 sX17ls1} Then t
min (per(X) - t-1 per(X(lln»)=r". For AESm per(A) _ t-1
XES. t t
per(A(lln» =r" if and only if A= ; U,,+ t~lEl71.
References
1. R. A. Brualdi Matrices of zeros and ones w!th fixed row and column sum vectors, Linear Alg. and its Appl. 33, 159-231 (1980).
2. s.G. Hwang, A note on a conjecture on permanents Linear Alg. and its Appl. 76, 31-44(1986).
3. _ _, The monotonicity and the Dokovic conjecture on permanents of doubly stochastic matrices, Linear Algebra and its Appl. 79, 127-151 (1986).
4. w.B. Jurkat and H. J. Ryser, Term ranks and permanents of nonnegative matrices, Journal of Alg. 6, 342-357 (1967).
5. H. Mine, Permanents, Encyclopedia of Mathematics and its Applications, 6, Addison-Wesley, Reading, Mass., 1978.
6. H. Mine, Theory of permanents, 1978-1981, Linear and Multilin, Alg 12, 227-263(1983).
7. R. Sinkhorn, A problem related to the Van der Waerden permanent theorem, Linear and Multilin. Alg. 16, 167-173(1984).
Andong University Andong 760-380, Korea
