PERMANENTS OF DOUBLY STOCHASTIC KITE MATRICES
SUK-GEUN HWANG*, JAB-DON LEE+ AND HONG-SUN PARK
ABSTRACT. Letp, qbe integers such that 2~p, q~n, and let Dp,q denote the matrix obtained from In, the identity matrix of order n, by replacing each of the first p columns by an all l's vector and by replacing each of the first two rows and each of the last q-2 rows by an all l's vector. In this paper the permanent minimization problem over the face, determined by the matrix Dp,q, of the polytope of all n x n doubly stochastic matrices is treated.
1. Introduction
Let On denote the set ofalln x n doubly stochastic matrices. This setisknown to be a convex polytope of dimensionn2- 2n+1 in the Euclidean n2-space. For an n x n matrix A = [aij), the permanent of A, perA, is defined by
perA= L alu (1)a2u(2)··· anu(n), uESn
where Sn stands for the symmetric group on the set {I, 2, ... , n}.
For an n x n matrix A and for i,j E {I,2,··· ,n}, let A(ilj) denote the matrix obtained from A by deleting rowi and columnj. A square (0, I)-matrix D = [l4j] issaid to have total support if per D(ilj) > 0 for every (i,j) with dij >O. For an n x n (0, I)-matrix D with total support, let
O(D) = {X E OnlX ::; D},
Received January 6, 1998.
1991 Mathematics Subject Classification: 15A05.
Key words and phrases: permanent, doubly stochastic matrix.
*Supported in part by Ministry of Education through research fund, BSRI 96- 1402 and in part by TGRC.
+Supported by the Taegu University research grant, 1996.
whereX :s; D means that every entry ofX is less than or equal to the corresponding entry of D. Then O(D) forms a face ofOn and every face ofOn is defined in this fashion [2]. After the resolution of the van der Waerden conjecture [4, 5, 16], there have been made many efforts to minimize the permanent function over various faces ofOn [3, 6, 8, 9, 10, 11, 12, 13, 14]. Let p,(D) denote the minimum permanent over O(D). A matrix A E O(D) is called a minimizing matrix over O(D) ifperA = p,(D). The set of all minimizing matrices over O(D) is denoted by Min(D). In the literature, the problem of determining p,(D) and Min(D) is called the permanent minimization problemover O(D). The permanent minjmization problem for any (0,I)-matrix of ordern of whichn - 2of the rows are aliI's vectors has been studied by Minc[ll], and the problem for staircase matrices has been investigated by Hwang[8], where a staircase matrix is a (0,I)-matrix of the form
[~::: ~:~Dkl Dk2 Dkk~~]
withDij being a zero matrix ifi < j, and an all1's matrixifi ~ j.
Let
1 1 1 1
1 0
o 1
o 0 o 0
(1) Cn= 1 1 0 0 1 0
1 1 0 0 0 1
1 1 1 1 1 1
1 1 1 1 1 1
be of ordern, and for an integerp with 2:s;p :s;n - 1, let Cn,p denote the matrix obtained from Cnby replacing each of the first p columns
by an all1's vector. The permanent minimization problem for Cn and Cn,p has been done by Song [13, 14]. Let n be a fixed positive integer.
For positive integers p, q with p, q ::; n, let Dp,q denote the matrix obtained. from Cn by replacing each of the first p columns and each of the last qrows with an all 1's vector. In order to have this replacement make sense we assume thatp, q ~ 2. We callDp,q a kite matrixof type (P,q). Note that the matrices Cn and Cn,p are kite matrices of type (2,2) and (p,2) respectively. In this paper we deal with the permanent minimization problem over the faces ofOn determined by kite matrices.
Note that, ifp+q ~ n +1, then Dp,q is a staircase matrix, and the permanent minimization problem over O(Dp,q) reduces to the work in [8]. So, we assume that p+q ::;n in the sequel.
2. Preliminaries
Inthe sequel, let In denote the identity matrix of order n and let Jm,n denote the m x n matrix of 1'so The matrix In,n is denoted by In for brevity. Ann xn matrix is calledfully indecomposableifit does not contain an s x (n - s) zero submatrix. We start this section with some useful lemmas.
LEMMA 2.1 [7]. Let D = [dij ] be a fully indecomposable (0,1)- matrixandlet A = [aij] E Min(D). Then A is alsofullyindecompos- able, and moreover, for (i,j) with dij = 1, per A(ilj) ~ per A with equalityifaij > O.
LEMMA 2.2 [11]. Let D and A = [ ab··· ,an] be the same as in Lemma 2.1.Ifdl = ... = dr for some r ::; n, then the matrix obtained from A by replacing each of the first r columns by the average of al,··· ,ar is also a matrixin Min(D). A similar statement holds for rows.
The following Lemma is a direct consequence of Lemma 2.3 of [10]
and we omit the proof.
LEMMA 2.3. Let D = [dij ] be a (0,I)-matrix with total support of which the first p columns are identical and dll = ... = dl,p =
1,d1,p+l = ... = d1,n = O. Then
( )
P-l
p,(D) = p;1 p,(D(111)).
LEMMA 2.4 [13]. Let Cn bethe kite matrix of type (2,2) definedin (1). Ifn ~ 6, then
(c )= 2(n - 3)(n - 4)n-4 p, n (n _2)n-l which is attained uniquely at the matrix
_1_ [In-2,2 (n - 4)In-2]
n - 2 0 J2,n-2 .
3. Minimizing the permanent over n(Dp,q) We begin with the cases wheren is small.
LEMMA 3.1. Let Cn be the kite matrix of type (2,2).
(a) Ifn =4, then
(2) p,(C4 ) = (16a2 -lOa+3)/14= 0.10277···
where a = 0.30343··· is the the unique real root of the polynomial equation
(3) 28x3- 24x2+8x - 1= 0,
andthe minimum value is attained uniquely at the matrix
(4)
[
a a (3 0]
a a 0 f3
" { " { a a '
"{ "{ a a where (3=1 - 2a and "{=(1 - 2a}/2.
(b) Ifn= 5, then
(5) J.L(Cs)= (2650a2+147a - 9)/121= 0.04781···
where a = 0.29513· .. is the unique real root of the polynomial equa- tion
(6) 44x3- 16x2+9x - 1=0,
and the minimum valueis attained uniquely at the matrix
(7)
[
a a {3 0 a a 0 {3
a a 0 0
'Y 'Y a a 'Y 'Y a a where {3=1-2a and'Y=(1-3a)/2.
Proof (a) was proved in [11].
(b) Itis proved in [12] that
(8)
where a is the unique real root of the polynomial equation (6) which is attained uniquely at the matrix in (7). The expression (5) is just a simplification of (8) taking account of (6). 0
We now discuss our main problem of minimizing the permanent over the face O(Dp,q) ofOn. Recall that the integersp, q are restricted to satisfy p+q :s;n and p, q~ 2.
THEOREM 3.2. Let p+ q:S; nand p,q ~ 2. Then (D ) = 4(p - 1)!(q -1)!f(P )
J.L p,q pp-lqq-l ,q
where
ifp+q=n,
f(P,q) =
14 (16a1 2 - lOa+3),
121 (2650,21 +147')' - 9), ifp+q= n - 1,
ifp+q ::;n - 2,
2(m -l)(m - 2)7n-2 m7n+1
witha and ')' being the unique real roots ofthe polynomial equations (3) and (6) respectively, and m = n - p - q+2.
Proof We prove the theorem by induction on p + q. Ifp + q=4,
then p=q= 2 and Dp,q =Cn. Since
4(p -l)!(q -1)1 = 4(2 -1)1(2 -1)! = 1
pp-lqq-l 2121
andp,(Cn ) =f(2,2), our theorem holds for this case, and the induction starts. Suppose that p + q 2: 5 and that the theorem holds for p +
q - 1. Without loss of generality we can assume that p 2: 3. Let E =Dp,q(111). ThenE = Dr,s withr =p-1and s = q. By induction hypothsis , we have
(E) = 4(r -l)!(s -l)!f(r s).
p, r r - lss-l '
We claim that fer,s) = f(P,q). This equality is clear for the cases p+q=nor p+q=n-1, beca1.JSep+q=n if and only ifr+s=n-1 = (order of E) and p+q= n-1ifand only ifr+ s = n-2= (order of
E) -1. The equality for the case p+ q ::; n - 2 is also evident because (n-1) - r-s+2=n-p-q+2=m. Since
( l)P-l
p,(Dp,q) = p; p,(E) ,
by Lemma 2.3, we finally have
(D )= (P_l)P-l 4(P-2)! (q-l)!f(P )= 4(P-l)!(q-l)!f(P )
JL p,q P (P _ 1)p-2 qq-l ,q pp-lqq-l ,q ,
and the proof is complete. 0
THEOREM 3.3. Let p +q :::; n and p, q 2:: 2. Then O(Dp,q) has a unique minimizing matrixA. Ifp+q2:: n - 1, then
o o o
(1-2a)I7n
A=
1pJp -2,P
2a J.
p 'm,p
2-2ka J. 2aJ. 1 7
q P q'm -J'q,q-2
pq , q ' q
where k = 2 if p+q = n, and k = 3 if p+q = n - 1, and a is the unique realroot ofthe equation (3) if p+q= n, and ofthe equation (6) ifp+ q=n -1. Ifp+ q=n - 2, then
A=
pJ1 p - 2,p 2 J.
mp 'm,p
o
o
- - I ' mm-2 m mq2 J.q,7n
o o
-J1 q ,q-2
q where m = n - p - q+2.
Proof Again we use induction onp+q. The casep+q=4 is done in Lemmas 2.4 and 3.1. So, we let p+q 2:: 5. We may assume that p 2:: qwithout loss of generality. Thenp 2:: 3. Suppose first that q= 2.
Then m =n - p. Ifm =2, then O(Dp,2) has a unique minimizing matrix by the works in [11]. Since the matrix
-Jp-2,p1 0 p2;J2,p (1 - 2a)I2
---J2,p1-2a aJ2 p
with a being the unique real root of equation (3), has permanent (16a2 -lOa+3)/14, this matrix is the unique minimizing matrix and our theorem holds for this case. Ifm 2:: 3, then the proof reduces to the work in [14]. Finally, suppose thatq2:: 3. Let E = Dp,q(111). Then
E =Dp-I,q. By induction, f2(E) has a unique minimizing matrixG.
Ifp+q~ n -1, then (p-1)+q= (n-1) -1, and by induction
1 0
p _ 1Jp- 3,p-1 0
2a (1- 2a)Ik 0
G= --1A,P-I
p-
2 - 2kaJ. 2aJ. 1
p_ q q,p-I q q,k qJq,q-2
o o o
- - Im-2 m m
~J.mq q,m
o
G=
-Jq,q-21 q
wherem = (n-1)-(p-1)-q+2=n-p-q+2. LetA E Min(Dp,q) and letAl = A(~JpEBln-p). Then byLem.ma2.2, we haveAl E Min(Dp,q).
Let A2=AI(~IpEBln_p) and let B =A 2(1/1). ThenBE f2(E) and wherea andk are the same numbers statedinthe theorem. Ifp+q ::s;
n - 2, then (p-1)+q::S;(n -1) - 2, and by induction p _1 1Jp-3,p-1
- Jmp2 mp-, I
( )P-I ( ) P - I ( ) P - I
perB = -L- per AI(lll)= -L-
1 perAl = - p - p.(Dp,q).
p - l p - p - l
Thus, by Lemma 2.3, we have that perB = p,(E) andB E Min(E), and hence that B =G. Therefore A has the form
All 0 0
A= A2I (1- 2a)Ik 0
A3I 2a 1
-Jq,k -Jq,q-2
q q
ifp+q~n - 1, or
An o o
A= A21 - - Im-2 m 0 m
2 J 1
Om mq q,m qJq,q-2
ifp +q :::; n - 2. A similar argument applied to' Dp,q(nln) assures that An = (ljp) Jp-2,p, A 21 = (2ajp)Jk,p if p +q ?:: n - 1, and A 21 = (2jmp)Jm,p if p+q :::; n - 2. Then A31 = ((2 - 2ka)jpq)Jq,p
automatically, and the proof is complete. 0
ACKNOWLEDGMENTS. The authors would like to thank the referee for some valuable comments and for pointing out several typographical errors inthe original manuscript.
References
[1] R. A. Brualdi,An interesting face of the polytope of doubly stochastic matrices, Linear and Multilinear Algebra 17 (1985), 5-18.
[2] R. A. Brualdi and P. M. Gibson, The convex polyhedron of doubly stochastic matrices: 1. Applications of the permanent function, J. Combin. Theory (A) 22 (1977), 194-230.
[3] R. A. Brualdi and B. L. Shader, Minimum permanents on special faces of the polytope of doubly stochastic matrices, Linear Algebra Appl. 201 (1994), 103-111.
[4] G. P EgoryCev, ReSnie problemy van-der- Vardena dla permanentov, Dokl Akad. Nauk SSR 258 (1981), 1041-1044.
[5] D.I.Falikman, Dokazatel'stvo gipotezy van der Vardena0 permanente dVaZdy stochasticeskeYl matricy, Mat. Zam. 29 (1981), 931-938.
[6] Ismor Fischer and Suk-Geun Hwang, Certain nonbarycentric cohesive matri- ces, Linear Algebra Appl. 239 (1996), 185-200.
[7] T. H. Foregger, On the minimum value of the permanent of a nearly decom- posable doubly stochastic matrix, Linear Algebra Appl. 32 (1980),75-85.
[8] Suk-Geun Hwang, Minimum permanent on faces of staircase type of the poly- tope of doubly stochastic matrices, Linear and Multilinear Algebra 18 (1985), 271-306.
[9] ,Minimizing the permanent over some faces of the polytope of doubly stochastic matrices, Linear Algebra Appl. 219 (1995), 195-205.
[10] Suk-Geun Hwang and Sun-Jeong Shin, A faces of the polytope of doubly sto- chastic matrices associated with certain matrix expansions, Linear Algebra Appl. 253 (1997), 125-140.
[11] H. Minc, Minimum permanents of doubly stochastic matriceswithprescribed zero entries, Linear and Multilinear Algebra 15 (1984),225-243.
[12] Seok-Zun Song, Minimum permanents on certain faces of matrics containing an identity S'Ubmatrix, Linear Algebra Appl. 108 (1988),263-280.
[13] , Minimum permanents on certain doubly stochastic matrices, Linear Algebra Appl. 143 (1991),49-56.
[14] ,Minimum perma'T/,ents on certain doubly stochastic matrices Il, Linear Algebra AppI. 161 (1992), 265-277.
[15] R. Sinkhorn and P. Knopp, Concerning nonnegative matrices and doubly sto- chastic matrices, PacificJ. Math 21 (1967), 343-348.
[16] B. L. Van der Waerden, Aufgabe 45, Jahresber. Deutch. Math.-Verein 35 (1926), 117.
Suk-Geun Hwang
Department of Mathematics Education Kyungpook National University
Taegu 702-701, Korea Jae-Don Lee
Department of Mathematics Education Taegu University
Taegu 705-714, Korea Hong-Sun Park
Department of Mathematics Graduate School
Kyungpook National University Taegu 702-701, Korea
