Permanents of doubly stochastic Ferrers matrices

J. Korean Math. Soc. 36 (1999), No. 5, pp. 1009-1020

PERMANENTS OF DOUBLY STOCHASTIC FERRERS MATRICES

SUK-GEUN HWANG AND SUNG-SOO PYO

ABSTRACT. The minimum permanent and the set of minimizing matrices over the face of the polytopeQ_n ofall doubly stochastic matrices of order n determined by any staircase matrix was deter- minedin [4] in terms of some parameter called frame. A staircase matrix can be described very simply as a Ferrers matrix by its row sum vector. Inthis paper, some simple exposition of the permanent minimization problem over the faces determined by Ferrers matri- ces of the polytope of^Qn are presentedinterms of row sum vectors along with simple proofs.

1. Introduction

For an ⁿ x ⁿ matrix A = ^[aij], the^permanentofA, perA, is defined by

perA=

L

UE8n

where Sn stands for the symmetric group on the set {I, 2,··· ,n}. Let Ondenote the polytope consisting ofalln x n doubly stochastic matrices.

For an n x n (O,l)-matrix D = [dij ] with perD

t-

OnlX :::; D} where X :::; D denotes that every entry ofX is less than or equal to the corresponding entry ofD. Then O(D) forms a face of On and every face ofOn is defined in this fashion [1]. Let JL(D) denote the minimum permanent over O(D). A matrix A E O(D) is called a minimizing matrix overO(D) ifperA= JL(D). A square (O,l)-matrix D

Received June 15, 1999.

1991 Mathematics Subject Classification: 15A15, 15A51.

Key words and phrases: permanent, staircase matrix, Ferrers matrix, doubly sto- chastic matrix.

This research was supported by TGRC-KOSEF.

1010 Suk-Geun Hwang and Sung-Soo Pyo is called a staircase matrix if it is partitioned as

D =

[~: ~~

~~]

Du Dk2 ••• D_kk

where D_ij is a zero matrixifi <-j and D_ij is an all1's matrixifi ~ j.

Suppose that D_ij is of sizePi xqj for all i,j = 1,2, ... ,k. For a (0,1)- matrixD, the matrixAD defined by

A_D = _per1DLp,

p

where the summation runs over all permutation matrices P satisfying P :::; D, is the barycenter of O(D). In [4] the problem of minimizmg the permanent function over the faces O(D) of On for staircase matrices D is investigated, and the minimum permanent, minimizing matrices and the barycenter of O(D) are determined in terms of numbers ni and 1ri

defined by the numbers.Pi, qj such as

i i-I

ni= L lJi - L P i l 1r=:=ni - qi (i

==

j=1 j=1

for any staircase matrix D with the above mentioned partition. The expressions of various quantities and the proofs in [4] look rather com- plicated and uncomfortable to apply to some other combinatorial prob- lems. In this paper we give some simple expressions and proofs for the results in [4], mainly in terms of row sums of the staircase matrix D considered.

2. The minimum permanent

From now on in the sequel, for ann x n matrix A,.and for subsets K, L of {1,2,'" ,n},letA(KIL) denote the matrix obtained fromA by deleting rows in K and columns in L. D is called barycentricifAD is a minimizing matrix over O(D). We start this section with a lemma which is essentially the same as Lemma 3.3 of [5], and we omit the proof.

Permanent of doubly stochastic Ferrers matrices 1011 LEMMA 1. Let D be a fully indecomposable (0, I)-matrix of which the first row contains exactly t 1 's in the first t positions and thefirstt columns are identIcal, and let E = D(111). Then

(a) J,t(D) = _(t~1

)t-l

(b) D is barycentricifand only if E is barycentric.

Let rI, rz, ... ,rn be integers with rl

s:

s: ... s:

s:

s:

1,2"" ,n) is a Ferrers matrix and is deIioted by F(rh rz,'" ,rn ). An n x n staircase matrix with row sum vector (rh rz,'" ,rn ) is just the Ferrers matrix F(rh rz, ... ,rn). It is well known (see Corollary 7.2.6 of [IJ for example) that

n

perF(rh rz,'" ,rn ) =

IT

⁺

i=1

IfF(rhrz, .. , , rn) ^is fully indecomposable, then, clearly,

n

perF(rh rz,'" ,rn ) =

IT

⁺

i=1

In the sequel, let r.pdenote the function defined on {I, 2"" } by

(

k

_l)k-l

r.p(k) = - k -

with the conventional assumption that 0°=1. In the following theorem, the minimum permanent over n(D), for a Ferrers matrix D, isgiven in terms of row sums. It is clear from Lemma 1 that a Ferrers matrix is barycentric.

THEOREM 2. Let D = F(r!>^TZ,'" ,rn ) be fully indecomposable.

Then

n

J,t(D) =

IT

⁺

i=1

Proof We use induction on n. Ifn = 2, thenD = F(2,2). We know that J,t(F(2,2» = 1/2. On the other hand,

z

(1)1(0)0 1

IT

⁺

2 i 2'

1012 Suk-Geun Hwang and Sung-Soo Pyo

and the induction starts. Let n > 2.· Let E = D(111). Then E = F(r2 -1, r3 - 1,··· ,rn -1). Now, by induction, we have

n~ n

p,(E) =

IT

+

IT

⁺

i=l i=2

Thus, by Lemma 1, it follows that

n

p,(D) =cp(rI)p,(E) =

IT

⁺

i=l

and the proof is complete.

o

(1)

By Lemma 1 (b) and by induction, we see that a Ferrers matrix.

is barycentric. Inwhat follows we give a formula for the entries of the barycenter off2(F(rbr2,··· ,rn)), in terms of the row sumsrb r2,··· ,rn- We first prove the following

LEMMA 3. Let D be a fully indecomposable (0, l)-matrix of which the first row contains exactlyt 1'sin the first t positions and the firstt columns are identical, and let E = D(111). Then

AE = ^[AD(111)]

C ~

Proof. LetAD= [,Bu], and for the consistency of positions with those ofD, let the rows and columns of E and A_E be indexed by 2, ... ,nas

[

e22 e23 ... e2n]. ['22 123 12n]

e32 e33 . . . e3n 132 133 13n

E= .._.. . .... . . . ... . , A.. E = . . . . '....

en2 ^{€M '"} enn 1n2 1n3 1nn

We make use of the following well known formula for f3ij and 1ij;

dij eij

(2) f3ij

=

=

pff pff

Notice that

(3) perD= t perE.

Permanent of doubly stochastic Ferrers matrices 10.13 Let (i,j) be such that eij =1 or, equivalently, dij =1. We show that

{

f3ij, ifj > t,

'Yij = _t_a .. if .<t

t - 1^f-'ZJ' J - .

Suppose first that j >t. Then the matrixD(ilj)still has the property that the first t columns are identical and the first row has t 1's in the first t positions, so that

(4) perD(ilj)

I::

p=!

= ^t perD(l,ilp,j) =^t perE(ilj).

Thus f3ij = ^'Yij by (2) and (3). Suppose now that j ::; t. Since the first t columns ofD are identical and the first row ofD hast 1's in the first t positions, we have

t

perD(ilj) =perD(ill) = LperD(l,iI1,p)

p=2

=(t - l)perD(l, ill,2) =(t - 1)perE(iI2)

=(t - l)perE(ilj).

Thus by (2) and (3) again, we have 'Yij = t f3ij/(t - 1) and we are

done. 0

For a fully indecomposable Ferrers matrix F = F(r!, r2,'" ,rn ) -

[!ij], and for a position (P, q), let

(5) €F(q) =min{il!iq= 1}.

Then clearly€F(q) <p. Let flp,q(F) denote the matrix obtained from F by applying the following two operations consecutively;

(i) Replace row i by a zero vector if i ~ {€F(q), €F(q)

+

With the above notations in mind, we now prove the following

THEOREM 4. Let D = F(r!, r2,'" ,rn ) = [dij], and let AD = [f3ij].

Then

(6) d ^{p .}

(3_pq ^=~

IT

r - p r· - 1,

+

p i=€F(q) Z

1014 Suk-Geun Hwang and Sung-SOD Pyo

for p, q= 1,2,··· ,n, where €D(q) isthenumber defined by (4).

Proof Let (p, q) be given and fixed. Ifdpq

=

= o.

So, suppose that dpq ⁼ 1 which is equivalent to that q S r^p. For the proof of this theorem, for a fully indecomposable Ferrers matrix F = F(tI,t_{2,· ..} ,t_n), let !p,q(F) denote the number defined by

p t· - i

jp,q(F) =

IT

~i+

i=€F(q) ^Z

To prove (5), we may show that (3pq = jp,q{D)/(rp - p), instead. Let

(SI,S2,··· ,sn)be the row sum vectors of~p,q(D). ThenSi = ri - i

+

Note also that .

p

f:_p,q(D)=

IT

i=€D(q) ^Z

CASE (i): p = 1. Clearly, {31q = 1/r1' because the first row of D equals (1,· .. ,1,0,··· ,0) in which the number of 1'sis ^rh and each of the first r1 columns of D is the all 1's vector. On the other hand, we have

~l,q(D)

[~

~ ~

~],

o ...

where the first row has sum T1. Thus it follows that jp,q(D) = (r1 - 1)/r1 = (Sl - 1)/Sl so that (31q = jp,q{D)/(Sl - 1), and we are done for this case.

CASE (ii): p 2: 2. Let E = D(111) and let AE = h'ii]. For the consistency of positions with those of Dagain, let E andA_E be indexed by 2, ... ,nas.in (1). Let (SI, S2,··· , sn) and (X2,··· , xn) be row sum vectors_of~p,q(D) and_~,q(E)respectively. Then clearly(X2' ... ,xn)~ (S2,··· ,sn). We divide the proof into the following two subcases.

Subcase. 1: T1 < q. In this case Sl = 0, and €D(q) = €E(q), so that jp,q(D) = jp,q(E). By induction we get lpq = jp,q(E)/(xp - 1) =

jp,q(D)/(sp-1). Since{3pq =lpq by Lemma 3, the assertion of Theorem 4 for this case follows.

Permanent of doubly stochastic Ferrers matrices

Subcase. 2: T1 ;::: q. In this caseED(q) = 1 and ED(q)-= 2, and

p p 1

f. (D) =

IT

IT

p,q ^{8' 8 X' 8} p,q

i=l z 1 i=2 z 1

1015

By Lemma 3 and by induction, we have

(3 - T1 - 1 _ 81 - 1 _ 81 - 1!p,q(E) _ !p,q(D)

pq - - - " ' { p q - - - " ' { p q - - - - ,

T1 81 81 Xp - ^{1 8}p - 1

and we are done. D

EXAMPLE 1. Let D= F(2,3, 5,6,6,8,8,8), i.e., 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0

(7) D= 1 1 1 1 1 1 0 0

= [dij ].

1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Let us find, say, the (6, 4)-entry /364 of the barycenter AD of O(D).

We take p=^{6, q}=4. Looking up the column q(=^{4) ofD,} we see that the smallest numberi such that_~6

i=

=

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Finally replace each of the l's below the main diagonal of this matrix by a 0, to get

1016 Suk-Geun Hwang and Sung-Soo Pyo

0 0 0 0 0 0 0 0

o

o

o

We see that (53,54, Ss, 56) = (3,3,2,3), and

(364

=

rr

^=!

^{~~!~ =~.}

Inthis way ADcan be calculated as

1/2 1/2 0 0 0 0 0 0

1/4 1/4 1/2 0 0 0 0 0

1/12 1/12 1/6 1/3 1/3 0 0 0

1/18 1/18 1/9 2/9 2/9 1/3 0 0 (8) AD= ^{1/18 1/18 1/9 2/9 2/9 1/3 O· 0}

1/54 1/54 1/27 2/27 2/27 1/9 1/3 1/3 1/54 1/54 1/27 2/27 2/27 1/9 1/3 1/3 1/54 1/54 1/27 2/27 2/27 1/9 1/3 1/3

We close this section with a property of the barycenter ofD(F(rbr2,'" ,

rn )). The following lemmaisdue to Foregger [3J.

LEMMA 5. Let D = [t.4j] be a fully indecomposable square (0,1)- matrixandlet A = [aijJ be a m;n;m;zing matrix overD(D). Then A is fullyindecomposable and, for (i,j) such that dij = 1, perA(i/j) 2: perA with equality ifaij> O.

THEOREM 6. Let D

=

=

i+1 for some i and let t be the smallest ofsuch i'sso that AD has the form

(9)

with U being of sizet x (t

+

+

Ul,U2 , ' •• ,Ut+1 have the same permanent.

Permanent of doubly stochastic Ferrers matrices 1017

Proof. We use induction on n. Ifn .- 1, the theorem clearly holds. If the zero submatrix in the upper right corner of (8) is vacuous, thenU is of size (n - 1) x n and

Since x > 0 and since Uj = AD(nlj) for j = 1,2,··· ,n, the assertion of the theorem for this case follows by Lemma 5 because a Ferrers is barycentric. Suppose that the zero submatrix in (8) isnot vacuous. Let

8 be the number of l's in the last column of D and let E = D(nln).

Then, by Lemma 3, we have

A^E =

(In-s

_~

Is)

Since the rowt ofE still has sumTt =t

+

A_[UO]

E -

* * '

the assertion of the theorem for this case follows by induction. 0

4. The structure of minimizing matrices overQ(F(Tl, T2,'" , Tn ))

In this section, we give a description of the structure of minimizing matrices overQ(D) for fully indecomposable Ferrers matrices Dinterms of row sums. The following lemmais due to Minc [6].

LEMMA 7. Let D be a (0, I)-matrix of which the first t columns are identical, and let A be a minimizing matrix over Q(D). Then the matrix obtained from A by replacing each of the first t columns by the average ofthose is also a minimizing matrix over Q(D). A similar statement holds for rows.

In the sequel, for a fully indecomposable Ferrers matrix F = F(81, 82,' .. ,8n ), let 9t(F) denote the set of all G = {gij] E Q(F) with the property thatgij equals the(i,j)-entry ofAp for every(i,j) ~ UkET({k+

1, k

+

+

+

THEOREM 8. Let D = F(Tl, T2,'" , Tn ) be fully indecomposable.

Then Min(D) =9t(D).

1018 Suk-Geun Hwang and Sung-Soo Pyo

Proof Let E = D(111) and let A E U(D) be given. Let Al be the matrix obtained from A by replacing each of the first TI columns by the average of those columns. Then

(10) perAI =perAI(111),

(11)

because the first row ofAl equals(l/Tl, ... , 1/TI,0, ... ,0) and the first

TI columns of Al are identical. Let B be the matrix obtained from AI(111) by multiplying each of the first TI - 1 columns by Td(TI - 1).

Then we get, by (9),

perB=

(TIT~ 1)Tl-I

I.

We also have, by Lemma 3, that

(12) A ^E 9t(D) ifand onlyifB ^E9t(E).

Suppose that A E Min(D). Then it follows that Al E Min(D) by Lemma 7, and hence that B E Min(E) by Lemma 1 and (9). Now, by induction, we have that B ^E 9t(E) so that A ^E 9t(D) by (11).

Conversely, suppose that A E 9t(D). IfUkET({k

+

+

+

A_[UO]

D -

* * '

withU being of sizet x (t

+

A

= [~ g],

⁼ [~ g].

For j = ^{1,2,··· ,t}

+

+

+ ... +

+

+ ... +

Permanent of doubly stochastic Ferrers matrices 1019

equal to a same vector, say z. We have

t+l t+l

perA= "2:(perUj )(per[xj,C]) = (perUl) "2: per[xj,C]

j=l j=l

= (perUl)(per(z,C]),

where the second equality is due to Theorem 6. Similarly, perAl (perUl)(per[z,

CD

Min(D), and the proof is complete. 0

EXAMPLE 2. Let D be the matrix in (6). Since (rl'r2,'" ,TS) (2,3,5,6,6,8,8,8) we see thatT ={I, 2, 5}, and the positions inUkET( {k+

1, k+2, L,n}x{I, 2,L, k+1})are those astriskedinthe following matrix, 1 1 0 0 0 0 0 0

* *

* * *

* * *

* * *

* * * * * *

* * * * * *

* * * * * *

In view of (7) and Theorem 8, we conclude that a minimizing matrix overO(D) is a doubly stochastic matrix of the form

1/2 1/2 ^{0 0 0 0 0 0}

* *

* * *

* * *

* * *

* * * * * *

* * * * * *

* * * * * *

References

[1] R. A. Brualdi and P. M. Gibson, The convex polyhedron of doubly stochastic matrices: 1. Applications of the perm(Lnent function,J.Combin. Theory (A)22 (1977), 194-230.

1020 Suk-Geun Hwang and Sung-Soo Pyo

[2] R. A. Brualdi and H. J. Ryser, Combinatorial Matrix Theory, Encyclopedia of Math. and Its Appl. Cambridge University Press, New York, 1991.

[3] T. H. Foregger, On the minimum value of the permanent of a nearly decompos- able doubly stochastic matrix, Linear Algebra Appl. 32 (1980),75-85.

[4] S.-G. Hwang, Minimum permanent on faces of staircase type of the polytope of doubly stochastic matrices, Linear and Multilinear Algebra 18 (1985), 271-306.

[5] S.-G. Hwang and S.-J. Shin, A face of the polytope of doubly stochastic matrices associated with _cert~in matrix expansions, Linear Algebra Appl. 253 (1997), 125-140.

[6] H. Minc, Minimum permanents of doubly stochastic matrices .with prescribed zero entries, Linear and Multilinear Algebra 15 (1984), 225-243.

Department of Mathematics Education Kyungpook National University

Taegu 702-701, Korea

E-mail: [email protected] E-mail: [email protected]