Determinants, Choices and Combinatorics
Joseph Malkoun









§ 



 §.§ 


seccntformat#1
  
  





||
‖‖
plain
*resultTheorem
theoremTheorem[section]
proposition[theorem]Proposition
corollary[theorem]Corollary
lemma[theorem]Lemma
conjectureConjecture[section]

definition
definition[theorem]Definition
conventions[theorem]Conventions
notation[theorem]Notation

note
3pt
3pt



:
.5em


note
remark[theorem]Remark
remarks[theorem]Remarks
note[theorem]Note
aside[theorem]Aside
example[theorem]Example

plain 

*genericthm
namedthm[1]
  
   
  
















equationsection






.6exto 0pt-.23ex "16D





Department of Mathematics and Statistics

Faculty of Natural and Applied Sciences

Notre Dame University-Louaize, Zouk Mosbeh

P.O.Box: 72, Zouk Mikael,
Lebanon
joseph.malkoun@ndu.edu.lb



Determinants, Choices and Combinatorics
    J. Malkoun
    Received: date / Accepted: date
=======================================



 We prove a formula which generalizes both Onn's colorful determinantal formula, related to Rota's basis conjecture, and Svrtan's n! formula, related to 
the Atiyah-Sutcliffe problem. In some cases, our formula allows us to prove some results similar in spirit to the statement of Rota's basis conjecture. 
We prove such a result using Svrtan's n! formula, generalizing one of Svrtan's arguments to a combinatorial setting.



Determinants, Choices and Combinatorics
    J. Malkoun
    Received: date / Accepted: date
=======================================





§ INTRODUCTION
 

In 1989, Rota conjectured his famous basis conjecture which, at the time of writing, is still open in general.

 Let V be a finite-dimensional vector space over a field 𝔽. Suppose, 1A,…,nA are n 
bases of V. Then for each i, there is a linear order of iA, say 

    1A = 
    {1a_1, 1a_2, …, 1a_n };  … ; nA = {na_1, na_2, …, na_n  },
 
such that 

    1C = {1a_1, 2a_1, …, na_1 };  …  ;nC = {1a_n, 2a_n, …, na_n }
 
are n bases.


The conjecture originated in Rota's work in invariant theory, and implies some identities in invariant 
theory and representation theory (cf. <cit.> and <cit.>). The literature 
surrounding Rota's basis conjecture is vast, and shall not be reviewed here. The reader may look for instance at <cit.>, <cit.>, 
<cit.>, <cit.>, <cit.>, <cit.> and the references therein.

We do mention though S. Onn's article <cit.>, where he proves his colorful determinantal formula, and uses it to show that the 
Alon-Tarsi conjecture on Latin squares implies Rota's basis conjecture for even n. The Alon-Tarsi conjecture on Latin squares states that if 
n is even, then the number of even n-by-n Latin squares is different from the number of odd n-by-n Latin squares. 

The Atiyah–Sutcliffe problem on configurations of points (<cit.>, <cit.> and 
<cit.>) is a geometric problem with roots in Physics (<cit.>). Indeed, in (<cit.>), Berry and Robbins 
propose a quantum-mechanical and geometric approach to the spin-statistics theorem, to be contrasted with the standard argument 
which relies on quantum field theory. Their discussion there was mostly for 2 or 3 identical particles. In order to extend their work to n 
identical particles, they needed a certain equivariant map to exist. This led to the so-called Berry-Robbins problem. 




Berry-Robbins Problem: Does there exist, for each n, a continuous map 

    f_n: C_n(ℝ^3) → U(n)/T^n

from the configuration space C_n(ℝ^3) of n distinct points in ℝ^3 into the complete flag manifold U(n)/T^n, such that 
f_n is equivariant under the action of the symmetric group Σ_n? More precisely, Σ_n acts on a configuration of n distinct points 
in ℝ^3 by permuting the n points of that configuration, while it acts by permuting the columns of an element of U(n), and this 
action induces an action on the quotient manifold U(n)/T^n.




In <cit.>, Atiyah solved positively the Berry-Robbins problem, but the maps f_n in that article were not 
very satisfactory: they were not smooth for instance. This led Atiyah to consider other candidate maps for f_n, which in 
turn led to the Atiyah-Sutcliffe conjectures, the area being sometimes referred to as the Atiyah-Sutcliffe problem on configurations of points. 
Consider n distinct points x_i in ℝ^3, for 1 ≤ i ≤ n. To each pair (i,j), 1 ≤ i,j ≤ n and 
i ≠ j, form the unit vector v_ij in the direction from x_i to x_j, and then let p_ij be the linear polynomial 
with root v_ij, after identifying the unit sphere of directions in ℝ^3 with the Riemann sphere using 
stereographic projection. For each i between 1 and n, denote by p_i the polynomial of degree less than n 
defined by

    p_i = ∏_j ≠ i p_ij

The polynomials p_i were conjectured by Atiyah in <cit.>, 
<cit.> to be linearly independent over ℂ, for any given configuration (x_i) of n distinct 
points in ℝ^3.  The conjecture 
was further refined by Atiyah together with Sutcliffe in <cit.>, where two 
successively stronger conjectures were also made. In 2018, linear independence was proved in <cit.>.

Svrtan in <cit.> considered not only the Atiyah-Sutcliffe determinant, relevant to the Atiyah-Sutcliffe conjectures, but also 
some modified determinant functions, corresponding to various subgraphs of the complete unoriented graph on n vertices, with 
the Atiyah-Sutcliffe determinant being one of them. There he proved his n! formula, which in particular shows that, given any 
initial configuration of n distinct points in ℝ^3, one of these 
modifed determinant functions must be non-zero.

In this article, we prove a formula (cf. Thm. <ref>) in section 2 generalizing both Onn's colorful determinantal formula in <cit.> and Svrtan's n! formula in <cit.>, and show 
how to obtain these two formulas as special cases in sections 3 and 4 respectively. In the process, we also generalize Svrtan's argument to a combinatorial setting (cf. Thm. <ref>).



§ AN IDENTITY INVOLVING PERMUTATION GROUPS AND DETERMINANTS
 

In this section, we introduce a general formula which includes as special cases Onn's colorful determinantal formula, as well as a formula by Svrtan, and more. Let 𝔽 be 
a fixed field. All matrices in this section will be assumed to have entries in the ground field 𝔽. Given a square matrix A of dimension 
n-by-n, we denote by [A] the n-tuple of its columns, namely [A] = (a_1,⋯,a_n), where a_i is the i-th column of A. Let 
1A,⋯,kA be k square matrices of dimensions n_1-by-n_1,..., n_k-by-n_k, respectively. Given the k-tuple of square matrices 
𝒜 = (1A,…,kA), we denote by

    [𝒜] = ([1A],…,[kA])

Let

    Σ = Σ_n_1×⋯×Σ_n_k
 
where Σ_n is the symmetric group on [n] = {1,…,n}. There is a natural action of Σ on the space of all k-tuples of square matrices as above. Namely, if 
σ∈Σ, we write σ = (σ_1,…,σ_k) where σ_i ∈Σ_n_i, and then define

    σ.𝒜 =  (σ_1.(1A),…,σ_k.(kA))

where 

    (ρ.A)_ij = A_i ρ^-1(j)    (1 ≤ i,j ≤ n)

for any n-by-n matrix A and any ρ∈Σ_n. 
Thus we see that an element σ∈Σ permutes the columns of each matrix 
iA, for 1 ≤ i ≤ k.

Let V^n denote the n-dimensional vector space 𝔽^n over 𝔽, and denote by V_n its dual vector space. Consider an element f of the following tensor product space:

    f ∈⊗_i=1^k (V_n_i)^⊗_n_i

where (V_n)^⊗_n denotes the n-th tensor power of the vector space V_n.
We denote by f(𝒜) ∈𝔽 the evaluation of the multilinear form f at the ordered set of column vectors of 𝒜 
(strictly speaking, one should write f([𝒜]) instead, but we simplify the notation by dropping the square 
brackets). Often in applications, one is interested in an alternating sum of the form

    ∑_σ∈Σsgn(σ) f(σ^-1.𝒜)

where

    sgn(σ) = ∏_i=1^k sgn(σ_i)

We have the following theorem.
 If 𝒜 = (1A,…,kA) is a k-tuple of square matrices and f as above, then

    ∑_σ∈Σsgn(σ) f(σ^-1.𝒜) = ℐ(f,𝐧) det(1A)⋯det(kA)

where det(A) denotes the determinant of a square matrix A, and ℐ(f,𝐧) ∈𝔽 is a scalar depending only on f and on the shape 
𝐧 = (n_1,…,n_k) of 𝒜.  

 As a corollary of the previous theorem, one can calculate ℐ(f,𝐧) by simply assuming that each iA is an identity matrix, for 1 ≤ i ≤ k. Namely, if we let

    I = (I_n_1,…,I_n_k)

where I_n_i denotes the n_i-by-n_i identity matrix, then

    ℐ(f,𝐧) = ∑_σ∈Σsgn(σ) f(σ^-1.I)
 

In applications, f is often a determinant, or a product of determinants (or sum thereof), which represents a combinatorial problem for which the 
input data 𝒜 has ambiguity, where the 
possible choices for 𝒜 are usually parametrized by the elements of Σ. The scalar ℐ(f,𝐧) represents a combinatorial invariant of the problem. 
If ℐ(f,𝐧) is non-zero, then for any input data 𝒜 (with ambiguity) for which all matrices 
iA are non singular for 1 ≤ i ≤ k (we will simply say in this case that 𝒜 is non-singular), the right-hand-side of (<ref>) is non-zero, 
which implies that one of the terms in the alternating sum on the left-hand side of (<ref>) is non-zero. 
This translates into the statement that, if ℐ(f,𝐧) ≠ 0, then given any non-singular input data 𝒜 with ambiguity, a choice 
for 𝒜 can be made so that some output matrix, or matrices, 
corresponding to f, are also non-singular. This is an outline of the general argument which will be made precise 
in the two applications we consider: Onn's colorful determinantal formula and Svrtan's n! formula, and their consequences.

  The (partial) skew-symmetrization of f belongs to the following 1-dimensional space

    ∑_σ∈Σsgn(σ) (σ.f) ∈⊗_i=1^k (Λ^n_i V_n_i)

where the action of Σ on elements

    f ∈⊗_i=1^k (V_n_i)^⊗_n_i
 
is given by (σ.f)(𝒜) = f(σ^-1.𝒜). But an element of Λ^n V_n is a scalar multiple of the n-by-n 
determinant, thought of as a multilinear form of the column vectors. We thus see, from equation (<ref>), that the alternating sum is some constant ℐ(f,𝐧) 
(constant meaning here independent of the values of the matrices iA) times 
the product of the determinants det(iA), for 1 ≤ i ≤ k. In other words, we have proved our main result, namely formula (<ref>).




§ ONN'S COLORFUL DETERMINANTAL FORMULA

In this section, we assume that the ground field 𝔽 is a field of characteristic 0, and that 𝒜 = (1A, …, nA), 
where each iA is an n-by-n matrix for 1 ≤ i ≤ n. We denote by 
iA^j the j-th column of the matrix iA. We define the multilinear form f by

    f(𝒜) = ∏_i=1^n det(1A^i, …, nA^i)

We introduce the group

    Σ = Σ_n ×⋯×Σ_n     (n factors)

where Σ_n is the symmetric group on [n]. We write an arbitrary element σ∈Σ as σ = (σ_1,…,σ_n).
We then form the alternating sum

    ∑_σ∈Σsgn(σ) f(σ^-1.𝒜) = 
    ∑_σ∈Σsgn(σ) ∏_j=1^n det(1A^σ_1(j), …, nA^σ_n(j))

By Thm. <ref>, we obtain that

    ∑_σ∈Σsgn(σ) f(σ^-1.𝒜) = ℐ(f,n) det(1A) ⋯det(nA)

It remains to calculate ℐ(f,n) using Cor. <ref>. We thus assume that

    iA = I_n     (1 ≤ i ≤ n)

where I_n is the n-by-n identity matrix. It can be shown that (cf. for instance <cit.> or <cit.>)

    ℐ(f,n) = ∑_σ∈Σsgn(σ) ∏_j=1^n det(e_σ_1(j),…,e_σ_n(j)) = l(n)

where l(n) is the number of even n-by-n Latin squares minus the number of odd n-by-n Latin squares. Combining the previous formula with formulas (<ref>) 
and (<ref>), we obtain Onn's colorful determinantal identity:

    ∑_σ∈Σsgn(σ) ∏_j=1^n det(1A^σ_1(j), …, nA^σ_n(j)) 
     = l(n) ∏_i=1^n det(iA)

 The Alon-Tarsi conjecture is that l(n) ≠ 0 if n is even. Onn used his formula to show that the Alon-Tarsi conjecture implies Rota's basis conjecture for even n, 
 which had been proved by Huang and Rota in <cit.>. The argument is as 
 follows. Assume n is even and that the Alon-Tarsi conjecture is true, i.e. that l(n) ≠ 0. If the matrices iA are non-singular for all i, 1 ≤ i ≤ n, then the right-hand side of 
 Onn's formula (<ref>) is non-zero, which implies that at least one of the terms in the alternating sum on the left-hand side of the same formula must be non-zero. But this is precisely the conclusion of 
 Rota's basis conjecture.



§ SVRTAN'S N! FORMULA

In this section, we choose to work over ℂ, though the results will all hold over any field 𝔽 of characteristic 0 (or more generally 
any field in which n! is non-zero). Inspired by both Rota's basis conjecture, as well as the Atiyah-Sutcliffe problem on configurations of 
points, the author came up with a hybrid problem, which he initially posted on an online forum (Math 
StackExchange at first, but then migrated to MathOverflow). The problem can be described as follows.

For m a positive integer, denote by V_m the space of complex polynomials of degree less than m in one complex variable. 
Let Γ_n be the complete oriented graph on n vertices. The set of vertices may be taken to be 
{1,…,n}, and the set of oriented edges becomes then 
{(i,j); 1≤ i,j ≤ n, i ≠ j}. We will denote the oriented edge (i,j) simply by e_ij. One may 
then introduce an equivalence relation ∼, where each e_ij is equivalent 
only to itself and to e_ji. We denote the equivalence class of e_ij by [e_ij], and the quotient 
Γ_n of Γ_n by ∼ is the non-oriented complete 
graph on n vertices, whose set of (non-oriented) edges is { [e_ij]; 1 ≤ i < j ≤ n }.


Assume there given, to each non-oriented edge [e_ij], i<j, of Γ_n, an 
ordered basis (ijp_1, ijp_2) of the space V_2. We call such an assignment an assignment of 
“spinor bases”. We refer to V_2 as the space of spinors. 

By an assignment c of spinors corresponding to an assignment of spinor bases, we mean that to each e_ij, with i < j, we assign either 
ijp_1 or ijp_2, and we assume that once such a choice is made, the “other” choice is made for the edge e_ji (i < j). 
So for instance, if to e_ij we assigned ijp_2, we must then assign ijp_1 to e_ji. Once an assignment of spinors is made, 
we denote the spinor associated to each edge e_ij (i ≠ j) simply by p^c_ij, where c refers to the assignment of spinors.

We denote by 𝒞 the set of all possible assignments of spinors (corresponding to some fixed assignment of spinor bases), which contains 
exactly 2^n2 elements. We define the sign sgn(c) of an assignment c ∈𝒞 of spinors to be 1 (resp. -1) if the 
number of times ijp_2 was assigned to the edge e_ij for i<j is even (resp. odd). We say that an assignment of spinors c is even 
(resp. odd) if sgn(c) = 1 (resp. sgn(c) = -1).

To each assignment c ∈𝒞 of spinors, one forms n complex polynomials p^c_i ∈ V_n, for 1 ≤ i ≤ n, of degree less than n 
in the complex variable t, obtained as follows. The polynomial p_i is defined as:

    p^c_i = ∏_j ≠ i p^c_ij    (1 ≤ i,j ≤ n)

The problem can now be stated.




Problem: Given an arbitrary inital assignment of spinor bases (ijp_1, ijp_2) to each non-oriented 
edge [e_ij], i<j, of the (non-oriented) complete graph Γ_n on n vertices,
does there always exist an associated assignment c of spinors to each oriented edge e_ij, i ≠ j, of the oriented complete graph Γ_n, 
for which the n polynomials p^c_i, for 1 ≤ i ≤ n, are linearly independent over ℂ?


 The answer to the previous problem is positive, namely, given any initial assignment 
of spinor bases to each (non-oriented) edge of Γ_n, there always exists an associated assignment 
c of spinors to each (oriented) edge of Γ_n, for which the associated n polynomials 
p^c_i, for 1 ≤ i ≤ n, are linearly independent over ℂ. 


Svrtan's theorem <cit.>, slightly modified to be adapted to our notation, can be written as follows:


    ∑_c ∈𝒞sgn(c) det(p^c_1,…,p^c_n) = n! ∏_1 ≤ i<j ≤ ndet(ijp_1, ijp_2)


 The proof follows from Thm. <ref>, with 𝒜 = ((ijp_1, ijp_2); 1 ≤ i<j ≤ n), and 

    f(𝒜) = det(p^c_0_1,…,p^c_0_n)

where c_0 ∈𝒞 corresponds to assigning ijp_1 to each e_ij, 1 ≤ i<j ≤ n (c_0 is thus even). Indeed formula (<ref>) then implies

    ∑_c ∈𝒞sgn(c) det(p^c_1,…,p^c_n) = ℐ(f,n) ∏_1 ≤ i<j ≤ ndet(ijp_1, ijp_2)

It remains only to check that ℐ(f,n) = n!. In order to calculate 
ℐ(f,n), it suffices by Cor. <ref> to assume that

    {[ ijp_1   = 1; ijp_2   = t ].

(1 ≤ i < j ≤ n). Given any (non-oriented) edge [e_ij] (i<j) of Γ_n, we orient it (i.e. assign to it a direction) from i to j 
(resp. from j to i) if ijp_1 = 1 is assigned to e_ij (ijp_2 = t is assigned to e_ij). We see that there must be exactly 
one vertex having exactly r outgoing vertices, for every r with 0 ≤ r ≤ n-1. Therefore only n! terms are non-zero in the alternating sum on the left-hand side of 
(<ref>), the ones corresponding to some complete order ≺ on the set [n] = {1,…,n}, with the corresponding assignment of spinors being

    i ≺ j ijp = 1

More precisely, (p^c_1,…,p^c_n) = 1 (resp. -1) if c corresponds to a complete order ≺ which in turn corresponds to an even (resp. odd) permutation of [n]. 
We therefore deduce that

    ℐ(f,n) = ∑_c ∈𝒞sgn(c) det(p^c_1,…,p^c_n) = n!

corresponding to the assignment of spinor bases in (<ref>). Svrtan's formula then follows, using equation (<ref>).


We can now prove Thm. <ref>. Indeed, given an assignment of spinor bases, it is clear that the right-hand side of Svrtan's n! formula (<ref>) is non-zero, so that 
one of the terms in the alternating sum on the left-hand side of the same formula must be non-zero. This implies that there is some associated assignment c ∈𝒞 of spinors, 
for which the polynomials p^c_1,…,p^c_n are linearly independent over ℂ, proving the theorem.

The author thanks Timothy Chow for an interesting email exchange
in which Dr. Chow informed the author about some of the 
literature surrounding Rota's basis conjecture, and suggested a line of attack similar to one 
initiated by Rota himself and applied to his conjecture, which had led 
to a link between his conjecture and the Alon-Tarsi conjecture concerning the number 
of even/odd latin squares of order n (cf. <cit.> for the original work, 
and <cit.> for a nicely written alternative short argument). The author is also indebted to the anonymous referee, who 
in particular provided a simpler proof of Svrtan's n! formula than the author's original 
proof, and this inspired the author to find a more general formula, using a similar idea.







.6exto 0pt-.23ex "16D






1

AL
Aharoni, R. and Loebl, M., The odd case of Rota's bases conjecture, Adv. Math. 282 (2015),
427-442.

Ati-2000
Atiyah, M. F., The geometry of classical particles, Surveys in differential geometry, 1 - 15, Surv. Differ. Geom., VII, Int. Press, Somerville, MA, 2000.

Ati-2001
Atiyah, M. F., Configurations of points, Topological methods in the physical sciences (London, 2000). R. Soc. Lond. Philos. Trans. Ser. A Math. Phys. Eng. Sci. 359 (2001), no. 1784, 1375–1387.

AM2018
Atiyah, M. F. and Malkoun, J., The Relativistic Geometry and Dynamics of Electrons, Found. Phys. 48:2 (2018), 199–208.

Ati-Sut-2002
Atiyah, M. F. and Sutcliffe, P. M., The geometry of point particles, R. Soc. Lond. Proc. Ser. A Math. Phys. Eng. Sci. 458 (2002), no. 2021, 1089–1115.

BR1997
Berry, M. V. and Robbins, J. M., Indistinguishability for quantum particles: spin, statistics and the geometric phase, Proc. Roy. Soc. London Ser. A 453 (1997), 1771–1790.

BD2015
Bollen, G. P. and Draisma, J., An online version of Rota's basis conjecture,  J. Algebraic Combin. 41 (2015), 1001–1012.

Chow1995
Chow, T., On the Dinitz conjecture and related conjectures, Disc. Math. 145 (1995), 73–82.

CFGV2003
Chow, T., Fan, C. K., Goemans, M. X. and Vondrak, J., Wide partitions, Latin tableaux, and Rota's basis conjecture, Advances Appl. Math. 31 (2003), 334–358.

C2009
Chow, T., Reduction of Rota's basis conjecture to a conjecture on three bases, Siam J. Disc. Math. 23 (2009), 369–371.

GH2006 
Geelen, J. and Humphries, P., Rota's basis conjecture for paving matroids, SIAM J. Discrete Math. 20 (2006), no. 4, 1042–1045.

GW2007
Geelen, J. and Webb, K., On Rota's basis conjecture, SIAM J. Discrete Math. 21 (2007), 802–804.

HR1994
Huang, R. and Rota, G.-C., On the relations of various conjectures on Latin squares and straightening coefficients, Discrete Math. 128 (1994), 225–236.

O1997
Onn, S., A colorful determinantal identity, a conjecture of Rota, and Latin squares, Amer. Math. Monthly 104 (1997), 156–159.

S2014
Svrtan, D., A Proof of All Three Euclidean Four Point Atiyah–Sutcliffe Conjectures, <https://www.emis.de/journals/SLC/wpapers/s73vortrag/svrtan.pdf>.

Zappa
Zappa, P., The Cayley Determinant of the Determinant Tensor and the Alon-Tarsi Conjecture, Adv. Appl. Math. 19 (1997), 31–44




