# Spectrum of Permanent’s Values and Its Extremal Magnitudes inΛn3 and Λn(α,β,γ)

Authors: Vladimir Shevelev
Journal: Journal of Optimization
 (2013)

---

## Abstract

LetΛnk denote the class of (0,1) square matrices containing in each row and in each column exactly k 1’s. The minimal value of k, for which the behavior of the permanent in Λnk is not quite studied, is k=3. We give a simple algorithm for calculation of upper magnitudes of permanent in Λn3 and consider some extremal problems in a generalized class Λn(α,β,γ), the matrices of which contain in each row and in each column nonzero elements α, β, and γ and n-3 zeros.


---

## Body

## 1. Introduction

The definition of permanent of a square matrixA=(ai,j) of order n is perA=∑‍∏i=1n‍ai,σ(i), where sum is over all permutations σ of numbers 1,…,n. This definition is very combinatorial. For example, if A is (0,1)-matrix, then perA is the number of arrangements of n nonattacking each other rooks on positions of 1’s of A. Therefore, the most natural applications of the permanent are in combinatorics: enumerating the Latin rectangles and squares, permutations with restricted positions, and different problems in the theory of graphs. Many interesting examples of applications of the permanent one can find in [1], chapter 8 (and not only in Mathematics!). To applications of the permanent there promoted celebrate proofs of the best known van der Waerden’s and Minc’s conjectures by Egorychev [2], Falikman [3], and Brègman [4], respectively. For example, Alon and Friedland [5] excellently used the Minc-Bregman inequality for permanent of (0,1)-matrices for finding the maximum number of perfect matchings in graphs with a given degree sequence.LetΛnk denote the class of (0,1) square matrices containing in each row and in each column exactly k 1’s. If A∈Λnk, then matrix k-1A is doubly stochastic, since all its row and column sums equal 1. Therefore, Λnk-matrices are also calleddoubly stochastic (0,1)-matrices. These matrices have especially simple and attractive structure and have many applications. It is important that especially class Λn3 in permanent’s history was a nontrivial test area for different researches of the permanent. For example, one can mention a remarkable Merriell research [6] of the maximum of permanent on class Λn3. An author’s research [7] of the permanent on Λ73-matrices (see Section 9) has led to the disproof of an important Balasubramanian conjecture [8] which would yield a full proof of 1967 Ryser hypothesis [9] on transversals of Latin squares.In the present paper we consider many other problems forΛn3. We study also the following natural generalization of Λn3. For given real or complex nonzero numbers α, β, and γ, denote by Λn(α,β,γ) the class of square matrices containing every number from {α,β,γ} exactly one time in each row and in each column, such that the other elements are 0’s. It is clear that, if A∈Λn(α,β,γ) and α+β+γ≠0, then the matrix (α+β+γ)-1A is doubly stochastic.Definition 1.
One callsp-spectrum in Λnk (denoting it ps[Λnk]) the set of all the values which are taken by the permanent in Λnk.Note thatp-spectrum in Λn1 trivially is {1}. It is known (cf. Tarakanov [10]) that
(1)ps[Λn2]={2,22,23,…,2⌊n/2⌋}.But, fork≥3,  p-spectrum of Λnk, generally speaking, is unknown. Greenstein (cf. [1], point 8.4, Problem 3) put the problem of describing the p-spectrum in Λn3. In this paper we give an algorithm for calculation of upper values of p-spectrum in Λn3. We also obtain several results for a generalized class Λn(α,β,γ) with real nonzero numbers α, β, and γ. Some results of the present paper were announced by the author in [11].


## 2. What Is Known aboutΛn3?

(1) Explicit formula for|Λn3| (cf. Stanley [12], chapter 1) is
(2)|Λn3|=6-n∑k1+k2+k3=n,ki≥0‍(-1)k2n!2(k2+3k3)!2k13k2k1!k2!k3!26k3.(2) Asymptotic formula for|Λn3| (cf. O’Neil [13]) is
(3)|Λn3|=(3n)!(36)ne-2(1+O(n-1+ε)),
where ε>0 is arbitrarily small for sufficiently large n.In addition, note that|Λn(α,β,γ)| with different α, β, and γ is, evidently, the number of 3-rowed Latin rectangles of length n such that
(4)|Λn(α,β,γ)|=n!Kn,
where Kn is the number of reduced 3-rowed Latin rectangles with the first row {1,2,…,n}. It is known (Riordan [14], pp. 204–210) that
(5)Kn=∑k=0⌊n/2⌋‍(nk)Dn-kDkUn-2k,
where Dn is subfactorial:
(6)D0=1,Dn=nDn-1+(-1)n,n≥1,
and {Un} is sequence of Lucas numbers of the Ménage problem which is defined by Cayley recursion (cf. [14], p. 201)
(7)U0=1,U1=-1,U2=0,Un=nUn-1+nn-2Un-2+4(-1)nn-2,n≥3
(see [15], sequences A102761, A000186).Denote, furthermore, byΛ¯n3 the set of matrices in Λn3 with 1’s on the main diagonal. Note that
(8)ps[Λn3]=ps[Λ¯n3].Indeed, it is well known that everyΛn3-matrix A has a diagonal of ones (i.e., a set of 1’s not two in the same row or column). Let l be such a diagonal. There exists a permutation of rows and columns π such that π(l) will be the main diagonal of π(A). Nevertheless, per(π(A))=perA and (8) follows.(3) A known explicit formula for|Λ¯n3| (Shevelev [16]) has a close structure to (5):
(9)|Λ¯n3|=∑k=0⌊n/2⌋‍(nk)Sn-kSkUn-2k,
where sequence {Sn} is defined by recursion
(10)S0=1,S1=0,Sn=(n-1)(Sn-1+12Sn-2),n≥2.(4) Asymptotic formula for|Λ¯n3| (Shevelev [16]) is
(11)|Λ¯n3|=Cn(ne)2n(1+O(n-1+ε)),
where
(12)C=2πe-5=0.29098…
and ε>0 is arbitrarily small for sufficiently large n.(5) Denote byΛ^n3 the set of symmetric matrices in Λ¯n3. P-spectrum on Λ^n3 is given by the following theorem (Shevelev [11]).Theorem 2.
LetR(n;3) denote the set of all partitions of n with parts more than or equal to 3. To every partition r∈R(n;3):n=n1+n2+⋯+nm, m=m(r), put in a correspondence the number
(13)H(r)=∏i=1ma(ni),
where sequence {a(n)} is defined by the recursion
(14)a(3)=6,a(4)=9,a(n)=a(n-1)+a(n-2)-2,n≥5.
Then one has
(15)ps[Λ^n3]={H(r):r∈R(n;3)}.(6) The maximal valueM(n) of permanent in Λn3 was found by Merriell [6].Theorem 3.
Ifn≡h(mod3), h=0,1,2, then
(16)M(n)=6(n-h)/3⌊(32)h⌋.Note that the caseh=0 of (16) easily follows from the Minc-Bregman inequality for permanent of (0,1)-matrices.(7) PutM(n)=M(1)(n). In case of n≡0(mod3), Bolshakov [17] showed that the second maximal M(2)<M(1)(n) of permanent in Λn3 (such that interval (M(2),M(1)) is free from values of permanent in Λn3) equals
(17)M(2)(n)={20,ifn=6,120,ifn=9,9166n/3,ifn≥12.Note that bothM(1)(n) and M(2)(n) are attained in Λ^n3.(8) Denote bym(n) the minimal value of permanent in Λn3. In 1979, Voorhoeve [18] obtained a beautiful lower estimate for m(n):
(18)m(n)≥6(43)n-3.This estimate remains the best even after proof by Egorychev [2] and Falikman [3], the famous van der Waerden conjectural lower estimate perA≥n!/nn for every n×n doubly stochastic matrix A. Indeed, this estimate yields only m(n)≥3n(n!/nn), such that (18) is stronger for n≥4.(9) Bolshakov [19] found p-spectrum in Λn3 in cases n≤8. Namely, he added to the evident p-spectrums ps[Λ33]={6} and ps[Λ43]={9} also the following p-spectrums:
(19)ps[Λ53]={12,13},ps[Λ63]={17,18,20,36},ps[Λ73]={24,25,26,27,30,31,32,54},ps[Λ83]={33,34,35,36,37,38,39,40,41,42,44,cccc45,48,49,52,72,78,81}.


## 3. A Generalization of Theorem2 on Matrices of Class Λn(α,β,γ) with Symmetric Positions of Elements

Denote byΛ¯n(α,β,γ) the set of matrices in Λn(α,β,γ) with β’s on the main diagonal. It is clear that, together with (4),
(20)|Λ¯n(α,β,γ)|=Kn.Note that, as for setsΛn3, Λ¯n3, we have
(21)ps[Λn(α,β,γ)]=ps[Λ¯n(α,β,γ)].Denote, furthermore, byΛ^n(α,β,γ) the set of matrices M={mi,j} in Λ¯n(α,β,γ) with symmetric positions of elements: mi,j=α if and only if mj,i=γ.P-spectrum on Λ^n(α,β,γ) is given by the following theorem.Theorem 4.
If to every partitionr∈R(n;3), n=n1+n2+⋯+nm, m=m(r), corresponds the number
(22)Hα,β,γ(r)=∏i=1ma(ni),
where sequence {a(n)=a(α,β,γ;n} is defined by the recursion
(23)a(3)=α3+β3+γ3+3αβγ,a(4)=α4+β4+γ4+4αβ2γ+2(αγ)2,a(n)=βa(n-1)+αγa(n-2)+αn-1(α-β-γ)+γn-1(γ-β-α),n≥5,
then one has
(24)ps[Λ^n(α,β,γ)]={Hα,β,γ(r):r∈R(n;3)}.Proof.
LetSn be the symmetric permutation group of elements 1,…,n. Two positions (i1,i2), (j1,j2) are called independent if ik≠jk, k=1,2. We will say that in the n×n matrix M={mij}, a weight mij is appropriated to the position (i,j). Let s∈Sn have no cycle of length less than n. Consider a map
(25)σ:(i,j)⟼(si(1),sj(1)),
appropriating to the position (si(1),sj(1)) the weight mij.
Now we need several lemmas.
Lemma A.(1) The mapσis bijective; (2) ifEis a set of pairwise independent positions, thenσ(E)is also a set of pairwise independent positions.
Proof.(a) Consider two distinct positions
(26)(i1,j1),(i2,j2),
such that, at least, one of the two inequalities holds
(27)i1≠i2,j1≠j2.
Let i1≠i2 such that, say, i1>i2. Show that si1(1)≠si2(1). Indeed, if we suppose that si1(1)=si2(1); then si1-i2=1;  that  is, s has a cycle of length i1-i2<n in spite of the condition. Conversely, if si1(1)≠si2(1), then i1≠i2, since s-1 has not any cycle of length less than n as well.
(b) Let positions (26) be independent. Both inequalities (27) hold and, as in (a), we have si1(1)≠si2(1), sj1(1)≠sj2(1); that is, the positions σ((i1,j1)), σ((i1,j1)) are independent as well.
Lemma B.Lets∈Snhave no cycle of length less thann. Then(0,1)-matrixShaving 1’s on only positions(28)(s1(1),s2(1)),(s2(1),s3(1)),…,(sn-1(1),sn(1)),(sn(1),s1(1))is an incidence matrix ofs.
Proof. Since s has no cycles of length less than n, then {s1(1),…,sn(1)} is a permutation of numbers {1,…,n}. Thus the set of positions of 1’s of matrix S coincides with the set of 1’s of the incidence matrix of s:(1,s(1)),…,(n,s(n)).
LetP=Pn be (0,1)-matrix with 1’s on positions (1,2),(2,3),…,(n-1,n),(n,1) only.
Lemma C.Lets∈Snhave not got any cycle of length less thann. IfSandS-1are the incidence matrices ofsands-1, then one has(29)σ-1(S)=P,σ-1(S-1)=P-1.Proof. Both formulas follow from Lemma B.
Noting thatσ(I)=I, where I is the identity matrix, we conclude that
(30)S-1+I+S=σ(P-1+I+P).
Moreover, since, by the bijection σ, to every diagonal (i.e., to every set of n pairwise independent positions) of the matrix αS-1+βI+γS corresponds one and only one diagonal of the matrix αP-1+βI+γP with the same products of weights, then we have
(31)per(αS-1+βI+γS)=per(αP-1+βI+γP).
Note that from the definition it follows that, for every matrix M∈Λ^n(α,β,γ), we have a representation
(32)M=αS-1+βIn+γS,
where S is the incidence matrix of a substitution s. In case when s has not got any cycle of length less than n, the matrix M is a completely indecomposable matrix in Λ^n(α,β,γ). Thus, by (31), all completely indecomposable matrices of Λ^n(α,β,γ) have the same permanent, equal to per(αP-1+βIn+γP).
In general, a substitutions with the incidence matrix S in (32) cannot have cycles of length less than 3. Indeed, if, for some i, we have either s(i)=i or s(s(i))=i, then in both cases s(i)=s-1(i) which means coincidence of positions 1’s of the matrices S and S-1 in the ith row.
Lets∈Sn be an arbitrary substitution with cycles of length more than 2. Let
(33)s=∏j=1rsj,
where sj∈Slj, lj≥3, and ∑j=1r‍lj=n, be the decomposition of s in a product of cycles. Then the matrix M=αS-1+βIn+γS is a direct sum of the matrices Mj=αSlj-1+βI+γSlj such that, by (31), perMj=per(αP-1+βIlj+γP) and we have
(34)perM=∏j=1rperMj=∏j=1rper(αP-1+βIlj+γP).
It is left to notice that Minc [20] found a recursion (23) for per(αIn+βP+γP2) and, as well known, the multiplication of an n×n matrix by P-1 does not change its permanent. Therefore, per(αP-1+βIlj+γP)=per(αIn+βP+γP2).Example 5.
Let us findps[Λ^11(-1,3,2)].We have the following partitions of 11 with the parts not less than 3:(35)11=8+3=7+4=6+5=3+4+4=3+3+5.
According to (23), for a(n)=a(-1,3,2;n), we have a(3)=16, a(4)=34 and for n≥5(36)a(n)=3a(n-1)-2a(n-2)+6(-1)n.Using induction, we find(37)a(n)={2n+1,ifnisodd,2n+1+2,ifniseven.Therefore,(38)ps[Λ^11(-1,3,2)]={a2a(11),a(3)a(8),a(5)a(6),cccca2(3)a(5),a(3)a2(4)}={4096,8224,8320,8704,16384,18496}.In the following examples we calculatep-spectrum for arbitrary n.Example 6.
Let us findps[Λ^n(-1,2,1)].By induction, fora(n)=a(-1,2,1;n), we have
(39)a(n)={2,ifnisodd,4,ifniseven.Further, again using induction, one can find that, ifn is even, then
(40)ps[Λ^n(-1,2,1)]={4,42,…,4⌊(n/4)⌋}
and, if n is odd, then
(41)ps[Λ^n(-1,2,1)]={2,2·4,2·42,…,2·4⌊((n-3)/4)⌋}.Example 7.
Analogously, in case ofΛ^n(-1,1,1), for a(n)=a(-1,1,1;n), we have
(42)a(n)={4,ifn≡0(mod6),-2,ifn≡3(mod6),1,otherwise,(43)ps[Λ^n(-1,1,1)]={{(-2)⌊((n-3)/3)⌋1,-2,4,…,(-2)⌊(n-3)/3⌋},ifn≡1,2(mod3),{1,-2,4,…,(-2)⌊(n-6)/3⌋,(-2)⌊n/3⌋},ifn≡0(mod3).It is interesting that, in case ofn multiple of 3, the permanent omits the value (-2)⌊(n-3)/3⌋.


## 4. Merriell-Type Theorems in a Subclass ofΛ^n(α,β,γ)

Note that in classΛn(α,β,γ) the Minc-Bregman inequality and the Merriell theorem, generally speaking, do not hold even for positive α, β,  and  γ. Nevertheless, some restrictions on α, β,  and  γ allow proving some analogs of the Merriell theorem. Recall that M(n) (16) is attained in Λ^n3. Denote by Mn(α,β,γ) the maximal value of permanent in Λ^n(α,β,γ).Theorem 8.
Consider a classΛ^n(α,β,γ) with the numbers α, β, and γ satisfying “triangle inequalities”
(44)0≤α≤β+γ,0≤γ≤α+β,
and the following additional conditions:
(45)a3(4)≤a4(3),αγ+β(a(3))1/3≤(a(3))2/3,
where sequence {a(n)} is defined by recursion (23). Then, for n multiple of 3, one has
(46)Mn(α,β,γ)=(a(3))n/3.Proof.
Note that conditions (44)-(45) are satisfied, for example, in case α=β=γ=1. Using induction, let us prove that
(47)a(n)≤(a(3))n/3.
Indeed, forn=3, this inequality is trivial, while, for n=4, it follows from the first condition (45). Let it hold for n≤m-1. Then, according to (23), we have
(48)a(m)=βa(m-1)+αγa(m-2)+αm-1(α-β-γ)+γm-1(γ-α-β)≤β(a(3))(m-1)/3+αγ(a(3))(m-2)/3=(a(3))(m-2)/3(β(a(3))1/3+αγ)≤(a(3))(m-2)/3(a(3))2/3=(a(3))m/3.
Note that, according to Theorem4, the equality in (47) holds in a direct sum of (3×3)-matrices of Λ^3(α,β,γ) which corresponds to the partition n=3+3+⋯+3. Let now A∈Λ^n(α,β,γ). By Theorem 4, there exists a partition of n with the parts not less than 3, n=n1+⋯+nm, such that
(49)perA=∏i=3ma(ni)
and, in view of (47), we have
(50)perA≤∏i=3ma(3)ni/3=(a(3))n/3.
This proves (46).Example 9.
Consider caseβ=γ-α.Let us find the values ofα, depending on the magnitude of γ, for which the conditions of Theorem 8 are satisfied. According to (23), we have
(51)a(3)=α3+(γ-α)3+γ3+3α(γ-α)γ=2γ3,a(4)=α4+(γ-α)4+γ4+4α(γ-α)2γ+2(αγ)2=2(α4+γ4).Thus the conditiona3(4)≤a4(3) means that α4+γ4≤21/3γ4 or
(52)0≤α≤(21/3-1)1/4γ=0.7140199⋯γ.
And it is easy to verify that the second condition in (45) is satisfied as well. As a corollary, we obtain the following result.Theorem 10.
If (52) holds, then, for n multiple of 3, one has
(53)Mn(α,γ-α,γ)=2n/3γn.Simple forms of sequence{a(n)} in Examples 5 and 6 allow supposing that in case β=γ-α (or symmetrical case β=α-γ) sequence {a(n)} keeps a sufficiently simple form. We find this form in the following lemma.Lemma 11.
Ifβ=γ-α, then sequence {a(n)} which is defined by recursion (23) has the form
(54)a(n)={2γn,ifnisodd,2(αn+γn),ifniseven.Proof.
Using induction with the base (51), suppose that (54) holds for m≤n. Then, by (23), for even n, we have
(55)a(n+1)=(γ-α)a(n)+αγa(n-1)+2αn(α-γ)=2(γ-α)(αn+γn)+2αγn+2αn(α-γ)=2γn+1,
while, if n is odd, then we have
(56)a(n+1)=2(γ-α)γn+2αγ(αn-1+γn-1)+2αn(α-γ)=2(αn+1+γn+1).Let now(57)α≥(21/3-1)1/4γ=0.7140199⋯γ.Theorem 12.
If (57) holds, then, for n multiple of 4, one has
(58)Mn(α,γ-α,γ)=(2(α4+γ4))n/4.Proof.
From (51) and (57), we conclude that
(59)a(3)≤(a(4))3/4.
Let us show that, forn≥3,
(60)a(n)≤(a(4))n/4.
Forn=4, inequality (60) is trivial. For n≥5, we have
(61)αn+γn=αn(1+(γα)n)≤αn(1+(γα)4)n/4≤(α4+γ4)n/4
and thus, using Lemma 11, we have
(62)a(n)≤2(αn+γn)<2n/4(α4+γ4)n/4=(a(4))n/4,n≥3.
Let nowA∈Λ^n(α,β,γ). By Theorem 4, there exists a partition of n with the parts not less than 3, n=n1+⋯+nm, such that
(63)perA=∏i=3ma(ni)
and, in view of (60), we have
(64)perA≤∏i=3ma(4)ni/4=(a(3))n/4
with the equality in a direct sum of (4×4)-matrices of Λ^3(α,β,γ) which corresponds to the partition n=4+4+⋯+4.Note that, ifα≠(21/3-1)1/4γ, then in Theorem 10 we have only maximizing matrix (up to a permutation of the rows and columns) which corresponds to the partition n=3+3+⋯+3; in Theorem 12 we also have only maximizing matrix (up to a permutation of the rows and columns) which corresponds to the partition n=4+4+⋯+4. It is interesting that, only in case of the equality α=θγ, where θ=(21/3-1)1/4, Theorems 10–12 are true for every n multiple of 12 with the equality of the maximums (2(α4+γ4))n/4=2n/3γn. Thus, up to a positive factor γ,  the class
(65)Λ^n(θ,1-θ,1),θ=(21/3-1)1/4,
possesses an interesting extremal property: it contains (n/12)+1 maximizing matrices (up to a permutation of the rows and columns), instead of only maximizing matrix, if θ≠(21/3-1)1/4.Indeed, the number of the maximizing matrices (up to a permutation of the rows and columns) is defined by the number of the following partitions ofn≡0 (mod 12):
(66)n=3+3+⋯+3,n=(4+4+4)+(3+⋯+3),…,n=4+⋯+4︸3i+3+⋯+3︸n-12i,i=0,1,…,n12.


## 5. Estimate of Cardinality ofP-Spectrum on Circulants in Λn3 and Λn(α,β,γ)

Denote byΔn3⊂Λn3 the set of the circulants in Λn3. Note that a circulant A∈Δn3 has a form A=Pi+Pj+Pk, 0≤i<j<k≤n, where P=Pn is (0,1)-matrix with 1’s on positions (1,2),(2,3),…,(n-1,n),(n,1) only. Multiplying A by P-i we obtain circulant B of the form
(67)B=In+Pr+Ps
with perB=perA. Since B is defined by a choice of two different values 0<r<k≤n, then trivially
(68)ps[Δn3]≤(n2)<n22.Now we prove essentially more exact and practically unimprovable estimate.Theorem 13.
One has(69)ps[Δn3]≤⌊n2+312⌋.Proof.
Let us return back to the general form(70)A=Pi+Pj+Pk,0≤i<j<k≤n.
Note thatA is defined by a choice of a vector (i,j,k), but its rotation, that is, a passage to a vector of the form (i+l,j+l,k+l)(modn), does not change the magnitude of perA. Indeed it corresponds to the multiplication A by Pl, and our statement follows from the equality per(PlA)=perA. Besides, its reflection relative to some diameter of the imaginary circumference of the rotation, by the symmetry, keeps magnitude of the permanent. Since geometrically three points on the imaginary circumference define a triangle, then our problem reduces to a triangle case of the following general problem, posed by Professor Richard H. Reis (South-East University of Massachusetts, USA) in a private communication to Hansraj Gupta in 1978:Let a circumference is split by the samen parts. It is required to find the number R(n,k) of the incongruent convex k-gons, which could be obtained by connection of some k from n dividing points. Two k-gons are considered congruent if they are coincided at the rotation of one relatively other along the circumference and (or) by reflection of one of the k-gons relatively some diameter.
In 1979, Gupta [21] gave a solution of the Reis problem in the form
(71)R(n,k)=12((⌊(n-hk2)⌋⌊(k2)⌋)+1kcccccc×∑d∣gcd(k,n)‍φ(d)(⌊(n-hk2)⌋⌊(k2)⌋nd-1kd-1)).
If we denote byΔnk⊂Λnk the set of the circulants in Λnk, then from our arguments it follows that
(72)ps[Δnk]≤R(n,k).
In case k=3, from (71)-(72) we find
(73)ps[Δn3]≤{n212,ifn≡0(mod6),n2-112,ifn≡1,5(mod6),n2-412,ifn≡2,4(mod6),n2+312,ifn≡3(mod6),
and (69) follows.Example 14.
In casen=5 we have only two incongruent triangles corresponding to circulants I5+P+P2 and I5+P+P3.Nevertheless, the calculations giveper(I5+P+P2)=per(I5+P+P3)=13. Thus ps[Δ53]={13}, and |ps[Δ53]|=1.Example 15.
In casen=6 we have three incongruent triangles corresponding to circulants I6+P+P2, I6+P+P3, and I6+P2+P4.The calculations giveper(I6+P+P2)=20 and per(I6+P+P3)=17,  while per(I6+P2+P4)=36. Thus ps[Δ63]={17,20,36}, and |ps[Δ63]|=3.Note that a respectively large magnitude ofper(I6+P2+P4) is explained by its decomposability in a direct product of circulants (I3+P+P2)⊗(I3+P+P2), such that per(I6+P2+P4)=(per(I3+P+P2))2=62=36.It is clear that, in case of circulants inΛn(α,β,γ), the upper estimate (69) yields either the same estimate, if α=β=γ, or ⌊(n2+3)/4⌋, if α=β≠γ (and in the symmetric cases), or ⌊(n2+3)/2⌋, if α, β, and γ are distinct numbers.Add that, using a bijection, one can apply formula (71) to enumerate the two-color bracelets of n beads, k of which are black and n-k are white (see, e.g., the author’s explicit formulas for sequences A032279-A032282, A005513-A005516 in [15]).


## 6. Algorithm of Calculations of Upper Magnitudes of the Permanent inΛ^n3

Theorem2 allows, using some additional arguments, giving an algorithm of explicit expressions of upper magnitudes of the permanent in Λ^n3 via numbers (14). For that we need the following lemma.Lemma 16.
Forn1,n2≥3, one has
(74)a(n1+n2)≤a(n1)a(n2),n1,n2≥3.Proof.
By the usual way, from (14) we find
(75)a(n)=φn+2+(-1)nφ-n,
where φ=(5+1)/2 is the golden ratio.
Denoteε(n)=(-1)nφ-n. Since n≥3, then |ε(n)|<0.24, and, consequently, if n=n1+n2, then (2+ε(n1))(2+ε(n2))>1.762>3. Therefore, we have
(76)a(n1)a(n2)=(φn1+2+ε(n1))(φn2+2+ε(n2))>φn1+n2+3>φn1+n2+2+ε(n1+n2)=a(n1+n2).Note that, actually, the difference between the hand sides of (76) is more than 1.76(φn1+φn2).Let nown≡j(mod3), j=0, 1, and 2, and t∈N. Let R(m;ν) denote the set of all partitions of n with parts more than or equal to ν. For us an important role play cases ν=3, 4. To r∈R(m;3), ρ∈R(m;4) put in a correspondence the sets
(77)Hm;3(r)={Πri∈rari},Hm;4(ρ)={Πρi∈ρaρi}.In casem=3, when ρ=∅, let us agree that H3;4 is a singleton {6}.Consider now the setLt(j)=Lt(j)(n):
(78)Lt(j)=⋃i=14t+j‍{6(n-j-3i)/3y:y∈H3i+j;4(ρ),y≥93t+j6i-4t-j}.Theorem 17 (algorithm of calculation of upper magnitudes of the permanent inΛ^n3).
Ifn≥4(3t+j), then the set Lt(j) taken in decreasing order of its elements gives |Lt(j)| upper magnitudes of the permanent in Λ^n3.Proof.
Note that the proof is the same for every value ofj. Therefore, let us consider, say, j=0. From (74) it follows that, if r∈R(n;3) contains λ3 parts 3 and λ3≤(n/3)-4t, then, for y∈Hn-3λ3;4(ρ), we have
(79)6λ3y≤6(n/3)-4t93t.
This means that, for the formation of the list of all upper magnitudes of the permanent in Λ^n3 in the condition n≥12t, which are bounded from below by 6(n/3)-4t93t, it is sufficient to consider only a part of the spectrum containing numbers {6λ3y}, where y∈Hn-3λ3;4(ρ) with the opposite condition λ3≥(n/3)-4t. From the equality 3λ3+⋯+nλn=n with the condition λ3≥(n/3)-4t, we have
(80)4λ4+⋯+nλn≤n-3(n3-4t)=12t.
Since 12t does not depend on n, there is only a finite assembly of such partition for arbitrary n. This ensures a possibility of the realization of the algorithm.
For the consideredr∈R(n;3), for λ3≥(n/3)-4t, we have Hn;3(r)=6(n-m)/3, where y∈Hm;4(ρ), and m has the form m=3i, 1≤i≤4t. Thus we should choose only Hn;3(r)≥6(n/3)-4t93t, and this yields
(81)y≥93t6(n/3)-4t=93t6i-4t,i=1,2,…,4t.In order to use Theorem17 for calculating the upper magnitudes M(1)(n)>M(2)(n)>⋯ of the permanent in Λ^n3, in case, say, n≡0(mod3),(1)
we write a list of partition of numbers3i, i=2,3,…,4t, with the parts not less than 4;(2)
we compare the corresponding values ofy with 93t6i-4t and keep only y≥93t6i-4t;(3)
after that, we take in decreasing order the numbers{y6(n/3)-i}.Below we give the first 10 upper magnitudesM^(1)>M^(2)>⋯>M^(10) of the permanent in Λ^n3, for n≥24, via numbers {a(n)} (14). Consider
(82)M^(1)={a(3)n/3=6n/3,ifn≡0(mod3),a(4)a(3)(n-4)/3=326(n-1)/3,ifn≡1(mod3),a(4)2a(3)(n-8)/3=946(n-2)/3,ifn≡2(mod3).Formula (82) shows that M(1)(n) is attained in Λ^n3. Moreover
(83)M^(2)={a(4)3a(3)(n-12)/3=9166n/3,ifn≡0(mod3),a(7)a(3)(n-7)/3=31366(n-1)/3,ifn≡1(mod3),a(5)a(3)(n-5)/3=1366(n-2)/3,ifn≡2(mod3);(84)M^(3)={a(6)a(3)(n-6)/3=596n/3,ifn≡0(mod3),a(4)4a(3)(n-16)/3=27326(n-1)/3,ifn≡1(mod3),a(8)a(3)(n-8)/3=49366(n-2)/3,ifn≡2(mod3);(85)M^(4)={a(4)a(5)a(3)(n-9)/3=13246n/3,ifn≡0(mod3),a(4)a(6)a(3)(n-10)/3=566(n-1)/3,ifn≡1(mod3),a(4)a(7)a(3)(n-11)/3=31246(n-2)/3,ifn≡2(mod3);(86)M^(5)={a(9)a(3)(n-9)/3=13366n/3,ifn≡0(mod3),a(4)2a(5)a(3)(n-13)/3=13166(n-1)/3,ifn≡1(mod3),a(4)5a(3)(n-20)/3=81646(n-2)/3,ifn≡2(mod3);(87)M^(6)={a(4)a(8)a(3)(n-12)/3=491446n/3,ifn≡0(mod3),a(5)2a(3)(n-10)/3=1692166(n-1)/3,ifn≡1(mod3),a(4)2a(6)a(3)(n-14)/3=546(n-2)/3,ifn≡2(mod3);(88)M^(7)={a(4)2a(7)a(3)(n-15)/3=31966n/3,ifn≡0(mod3),a(10)a(3)(n-10)/3=1252166(n-1)/3,ifn≡1(mod3),a(4)3a(5)a(3)(n-17)/3=39326(n-2)/3,ifn≡2(mod3);(89)M^(8)={a(4)6a(3)(n-24)/3=812566n/3,ifn≡0(mod3),a(4)a(9)a(3)(n-13)/3=13246(n-1)/3,ifn≡1(mod3),a(5)a(6)a(3)(n-11)/3=65546(n-2)/3,ifn≡2(mod3);(90)M^(9)={a(4)3a(6)a(3)(n-18)/3=5166n/3,ifn≡0(mod3),a(5)a(8)a(3)(n-13)/3=63712966(n-1)/3,ifn≡1(mod3),a(5)2a(4)a(3)(n-14)/3=1691446(n-2)/3,ifn≡2(mod3);(91)M^(10)={a(5)a(7)a(3)(n-12)/3=40312966n/3,ifn≡0(mod3),a(4)3a(7)a(3)(n-19)/3=31646(n-1)/3,ifn≡1(mod3),a(11)a(3)(n-11)/3=67726(n-2)/3,ifn≡2(mod3).


## 7. Main Conjectural Inequality for Maximum of Permanent in Completely IndecomposableΛn3-Matrices

Denote byΛn,13 the set of completely indecomposable matrices in Λn3, that is, the set of Λn3-matrices containing no Λm3-submatrices. Let μ1(n) denote the maximum of permanent in Λn,13. Our very plausible conjecture which we call “main conjectural inequality (MCI)” is the following.Conjecture 18 (cf. Shevelev [11], pp. 165-166).
Forn1,n2≥3, one has
(92)μ1(n1+n2)≤μ1(n1)μ1(n2).In Lemma16 we essentially proved that in subclass Λ^n3 the MCI is valid.Besides, in all known cases MCI holds. Moreover, as we shall see, our algorithm of calculation of the consecutive upper magnitudes(M=M1>M2>⋯) of permanent in Λn3, which is based on MCI, reproduces all Merriell’s and Bolshakov’s results for M1 and M2. Note also that, for sufficiently large n, the number of consecutive upper magnitudes of permanent in Λn3 grows very quickly with every step of extension of the list of known p-spectrums for small n. For example, using the found by Bolshakov ps[Λi3], i≤8, we obtain, for sufficiently large n, 4, 7, and 11 upper values of ps[Λn3] in cases n=3k, 3k+1, and 3k+2 respectively. Further, after calculating ps[Λ93], the number of upper values of, for example, ps[Λ3k3] increases by more than thrice.


## 8. Algorithm of Calculations of Upper Magnitudes of the Permanent inΛn3 Based on MCI

Letn≡j(mod3), j=0, 1, 2, and t∈N. Let R(m;ν) denote the set of all partitions of n with parts more than or equal to ν. For us an important role play cases ν=3,4. To r∈R(m;3), ρ∈R(m;4) put in a correspondence sets
(93)πm;3(r)={Πri∈rxri},πm;4(ρ)={Πρi∈ρxρi},
where xs runs through all values of permanent in set Λs,13 of completely indecomposable matrices in Λs3 (in case m=3, when ρ=∅, let us agree that π3;4 is a singleton {6}).Consider now the setEt(j)=Et(j)(n):
(94)Et(j)=⋃i=14t+j‍{6(n-j-3i)/3y:y∈π3i+j;4(ρ),y≥93t+j6i-4t-j}.Theorem 19 (algorithm of calculation of upper magnitudes of the permanent inΛn3).
Ifn≥4(3t+j), then the set Et(j) taken in decreasing order of its elements gives |Et(j)| upper magnitudes of the permanent in Λn3.Proof.
We need three lemmas.Lemma 20.
Forn≥4, one has
(95)μ1(n)≤3n/2.Proof.
Let, firstly,n≡0(mod4). Note that μ1(4)=D4=9. Using (92), we find
(96)μ1(n)≤μ1(4)μ1(n-4)≤⋯≤(μ1(4))n/4=3n/2.
Let, furthermore,n≡i(mod4), i=1, 2, 3. Note that, by (19), μ1(5)≤13<32.5. Therefore, using (92), we have
(97)μ1(n)≤(μ1(4))(n-5i)/4(μ1(5))i<3(n-5i)/232.5i=3n/2.Lemma 21.
Letn=3λ3+4λ4+⋯+nλn be a partition of n with the parts not less than 3. If λ3≤l and n has the form n=3l+4m, then, for completely indecomposable matrices Ai∈Λi3, i=3,4,…,n, one has
(98)∏i=3n‍(perAi)λi≤6l9m.Proof.
Using Lemma20, we have
(99)∏i=3n‍(perAi)λi≤6λ334λ4+⋯+nλn≤6l3n-λ3=634m=6l9m.Lemma 22.
Letn=3λ3+4λ4+⋯+nλn and
(100)λ3≤n-4j3-4t,n≥4(3t+j),
where t is a nonnegative integer and j is the residue of n modulo 3,  j=0, 1, 2; then, for completely indecomposable matrices Ai∈Λi3, i=3,4,…,n, one has
(101)∏i=3n‍(perAi)λi≤6((n-4j)/3)-4t93t+j.Proof.
Putl=((n-4j)/3)-4t, m=(n-3l)/4=3t+j. Now the lemma follows from Lemma 21.It is left to note that, after these lemmas, the proof of Theorem19 is the same as proof of Theorem 17.Note that the use of this algorithm is based on the upper values ofp-spectrum for smaller values of n.Consider, for example, caset=0, j=2. According to (94), we have
(102)E0(2)=⋃i=12‍{6(n-2-3i)/3y:y∈π3i+j;4(ρ),y≥81·6i-2}={6(n-5)/3perA,A∈Λ53:6perA≥81}∪{81·6(n-8)/3}.Note that the second set is a simpleton, since, by MCI,μ1(8,3)≤(μ1(4,3))2=81. Since, by (19), M(5)=13<81/6, then the first set in (102) is empty. Thus E0(2)=E0(2)(n) is simpleton:
(103)E0(2)={81·6(n-8)/3}
and we have
(104)M(1)(n)=81·6(n-8)/3,n≥8,
which corresponds to Merriell’s result in case n≡2(mod3).Further research of the set (94), using (19), gives the following results.(1) Considerj=0, n≥24:
(105)M(1)(n)=6n/3,M(2)(n)=9166n/3,M(3)(n)=596n/3,M(4)(n)=13246n/3.The continuation of this list requires knowingps[Λ93]. Note that a more detailed analysis shows that, after calculation of ps[Λ93], in this case one can obtain the first 12+|G| upper magnitudes of the permanent in Λn3, where G=ps[Λ93]∩([69,116]∖{72,78,102,108}).(2) Considerj=1, n≥28:
(106)M(1)(n)=326(n-1)/3,M(2)(n)=896(n-1)/3,M(3)(n)=31366(n-1)/3,M(4)(n)=27326(n-1)/3,M(5)(n)=566(n-1)/3,M(6)(n)=13156(n-1)/3,M(7)(n)=1692166(n-1)/3.It is interesting that in this caseps[Λ93] is not used up to M(7), but the continuation of this list requires knowing ps[Λ103].(3) Considerj=2, n≥32:
(107)M(1)(n)=946(n-2)/3,M(2)(n)=1366(n-2)/3,M(3)(n)=2·6(n-2)/3,M(4)(n)=1396(n-2)/3,M(5)(n)=49366(n-2)/3,M(6)(n)=436(n-2)/3,M(7)(n)=31246(n-2)/3,M(8)(n)=81646(n-2)/3,M(9)(n)=546(n-2)/3,M(10)(n)=1196(n-2)/3,M(11)(n)=39326(n-1)/3.Note that the method not only gives a possibility to calculate the upper magnitudes of the permanent inΛn3, but also indicates those direct products on which they are attained. For example, in (107) M9 is attained on direct products of some matrices Ai∈Λi3:(108)A8⊗A3⊗⋯⊗A3︸(n-8)/3,A4⊗A7⊗A3⊗⋯⊗A3︸(n-11)/3,A4⊗A4⊗A6⊗A3⊗⋯⊗A3︸(n-14)/3.Note also that the comparison of (105)–(107) with (82)–(91) shows that the following calculated M(i) are attained in Λ^n3, n≥32:in casen≡0mod3,
(109)M(1),M(2),M(3),M(4);
in case n≡1mod3,
(110)M(1),M(3),M(4),M(5),M(6),M(7)
(but M(2) is not attained);in casen≡2mod3,
(111)M(1),M(2),M(5),M(7),M(8),M(9),M(11)
(but M(3), M(4), M(6), andM(10) are not attained).


## 9. Algorithm for Testing the Parity of Values of the Permanent inΛn3

It seems that, among all known methods of calculation of the permanent, only Ryser’s method (cf. [1], chapter 7) could be used for creating an algorithm for testing the parity of values of the permanent. Let A be n×n-matrix. Let Ar be a matrix which is obtained by changing some r columns of A by zero columns. Denote by S(Ar) the product of row sums of Ar. Then, by Ryser’s formula, we have
(112)perA=∑S(A0)-∑S(A1)+∑S(A2)-⋯+(-1)n-1∑S(An-1).Let nowA have integer elements. Introduce the following matrix function:
(113)Υ(A)={1,ifallrowsumsofAareodd,0,otherwise.From (112) we have
(114)perA≡∑Υ(A0)-∑Υ(A1)+∑Υ(A2)+⋯+∑Υ(An-1)(mod2).Using (114), let us create an algorithm of a search of the odd values of the permanent in Λn3. Since, evidently, perA≡detA(mod2), then A should have pairwise distinct columns. Note that cases n≡j(mod 3), j=0,1,2, are considered by the same way. Suppose, say, n=3t. According to (114), we are interested in only cases when, after removing r≥1 columns of A, all row sums will be odd. Suppose that, after removing r columns of A, we have that p sums remain equal to 3 and n-p sums equal to 1. This means that the total number of the removed 1’s equals 2(n-p)=6t-2p. Since, removing a column, we remove three 1’s, then the number of the removed columns equals r=2t-((2p)/3). Thus p=3m and r=2(t-m), m=0,1,…,t-1. However, if m=t-1, then r=2. By the condition, these two columns are distinct; therefore, we conclude that at least one row sum equals 2. The contradiction shows that the testing sequence is r=4,6,…,2t. In cases n≡1,2(mod3) we obtain the same testing sequence.Example 23.
Let us check the parities of values of the permanent of circulants inΔ73⊂Λ73.In this caset=⌊7/3⌋=2 and, therefore, the testing sequence contains only term r=4. Note that matrix Ar has all odd rows if and only if one row sum equals 3 and each of the 6 other row sums equals 1. Indeed, let, after removing 4 columns of A, p sums remain equal to 3 and 7-p sums equal to 1. This means that the total number of the removed 1’s equals 2(7-p) and the number of the removed columns equals r=4=(14-2p)/3; that is, p=1. Moreover, since in a circulant all rows are congruent shifts of the first one, it is sufficient to consider the case when precisely the first row sum equals 3 and others equal 1 (the multiplication on 7 does not change the parity of the result). This opens a possibility of a momentary handy test on the parity every circulant of class Δ73. This test consists of removing all four columns beginning with 0. If now every row 2,…,7 has one 1, then the permanent is even; otherwise, it is odd. We check now directly that from (73)=35 circulants exactly 21 ones have odd permanent.Remark 24.
In 1967, Ryser [9] did a conjecture that the number of the transversals of a Latin square from elements 1,…,n (i.e., the number of subsets of its n pairwise distinct elements, with none in the same row or column) has the same parity as n. If n is even, then the conjecture has been proved by Balasubramanian [8]. Besides, in [8] Balasubramanian posed a conjecture for the parity of a sum of permanents, such that the truth of this conjecture yields Ryser’s hypothesis for odd n. In the same year (1990), using the result of Example 23, the author disproved Balasubramanian’s conjecture. It is interesting that soon Parker (see [22], p. 258) indeed found several Latin squares of order 7 with even number of transversals. Add that later ([7]) we found even an infinite set of counterexamples to the Balasubramanian conjecture.


## 10. Open Problems

(1)
To prove the MCI (Section7).
(2)
Consider classΛn(1,1+a,1+b), where 0≤a≤b<(4e-9)/6 (cf. [23], pp. 171-172). Since Λn(1,1,1)=Λn3, then Voorhoeve’s lower estimate (81/32)(4/3)n for permanent of Λn3-matrices trivially holds for matrices in Λn(1,1+a,1+b). It is clear that, for a>0,b>0, an essentially stronger lower estimate should exist. However, using van der Waerden-Egorychev-Falikman theorem to class Λn(1/(3+a+b),(1+a)/(3+a+b),(1+b)/(3+a+b)) of doubly stochastic matrices, for the permanent of Λn(1,1+a,1+b)-matrices, we obtain even weaker lower estimate of the order C1n((3+a+b)/e)n≪C(4/3)n in the case a+b∈(0,(4e-9)/3). The problem is to find a stronger lower estimate for the permanent in Λn(1,1+a,1+b) in this case.
(3)
LetM be a circulant of order n with integer elements (cf. [23], pp. 115-116). We conjecture that, for every integer m, we have perM≡(-1)nper(mJn-M)(modn), where n×n-matrix Jn consists of 1’s only. In [7] the conjecture was proved for every m and prime n. Thus the question is open in case of arbitrary composite number n.
(4)
Let us call two Latin rectangles equivalent if the sets of their elements in the corresponding columns are the same. Note that one can treat numbers|Λn3| as the numbers of equivalence classes of 3×n Latin triangles. Let A=In+P+P2. It could be proved that the cardinality of the corresponding equivalent class is 2n+6+2(-1)n. To find the cardinality of the equivalent class which is defined by matrix In+P+P3.



---

*Source: 289829-2013-11-17.xml*