Grassmann (or anti-commuting) variables are extensively used in theoretical physics. In this paper we use Grassmann variable calculus to give new proofs of celebrated combinatorial identities such as the Lindstrom-Gessel-Viennot formula for graphs with cycles and the JacobiTrudi identity. Moreover, we de ne a one parameter extension of Schur polynomials that obey a natural convolution identity.
8i; j = 1; : : : ; m: i2 = 0;
8i = 1; : : : ; m: More precisely, the Grassmann algebra m over the m anti-commuting variables f 1; : : : ; mg is de ned as the linear span of the 2m independent products of the i's. Its elements are functions of the form f ( ) = Xm 1
m! n=0
X 1 i1;::: in n ai1:::in i1 : : : in ; where ai1:::in are complex coe cients, antisymmetric with respect to their indices, ai (1);:::i (n) = ( )ai1;:::;in , and the vector space structure is simply de ned by addition and scalar multiplication of the coe cients. A function f which is a sum of only even (resp. odd) monomials is called even (resp. odd). The multiplication rule for monomials is ( i1 : : : in )( j1 : : : jp ) = ( 0 sgn(k) k1 : : : kn+p if fi1; : : : ; ing \ fj1; : : : ; jpg 6= ; ; otherwise (1) (2) (3) (4) with k = (k1; : : : ; kn+p) the permutation of (i1; : : : ; in; j1; : : : ; jp) such that k1 < : : : < kn+p. It is then extended to the whole Grassmann algebra by distributivity. For notational convenience, we will furthermore commute complex and Grassmann variables, and to permute the Grassmann variables themselves following the de ning rule (1).
ef( ) :=
f ( )p; X+1 1 p=0 p! which, following (1), is a simple polynomial expression. In particular one immediately nds that e i1 ::: in = 1 + i1 : : : in : Another interesting property is that eAeB = eA+B for any even Grassmann functions A and B (since A and B therefore commute).
Due to these multiple properties, Grassmann variables are extensively used in quantum eld theory to describe the physics of fermions1, which are particles obeying the so-called Fermi-Dirac statistics, statistics which is based on anti-commutation laws (unlike bosons2, which are particles obeying the Bose-Einstein statistics (statistics based on commutation laws), and which are described by physicists using usual commuting variables) { the interested reader is reported to quantum eld theory textbooks such as [FKT02] for more details.
The Grassmann integral R d
m to C s. t. Z d 1 : : : m = 1:
i1 : : : in = 0 whenever
n < m.
Example 1.1. Let and be two independent Grassmann variables (the bar has nothing to do with any complex conjugation) and let a 2 C. One computes:
Z d d e a =
Z
Z d d (1 a ) = d d ( a ) = a d d = a:
a = 1:
d N : : : d 1 (1) : : :
(N) = sgn( ): Z e
Z
Z where we have used the notation
d d := d N d N : : : d 1d 1: 1Example of fermions are: the electrons, the neutrinos, the quarks. 2Examples of bosons are: photons, gluons, Higgs bosons. (5) (6) (7) (8) (9)
Let M be an N dimensional square matrix whose entries are commuting variables (such as complex numbers). Its determinant can be expressed as a Grassmann Gaussian integral over 2N Grassmann variables i; i, i = 1; : : : ; N . As above, the conjugate notation conveniently accounts for the doubling of variables. Using the morphism property of the exponential on even functions, one proves: Similarly, one can express any minor of M using Grassmann calculus. Let 0 p N and let I = fi1; : : : ; ipg, J = fj1; : : : ; jpg be two subsets of indices of f1; : : : ; N g, where i1 < : : : < ip and j1 < : : : < jp. We denote by MIcJc the matrix obtained by deleting from M the rows with indices in I and the column with indices in J . One has det M = ( 1) I+ J det(MIcJc ) = d d Z i
0
N X i;j=1 0
1
J I :=
j1 i1 : : : jp ip : One can prove more general Grassmann Gaussian integral formulas3, such as: kMk`1 ` +
N X( k k + k k)A = det(M k=1 1
0
N X k;`=1 Let G be a nite directed graph. Note that we allow loops and multiple edges. Let V = fv1; : : : ; vN g be the set of vertices of G. One assigns to each edge e a weight we. One further assumes that the variables we commute with each others.
A path P from v to v0 is a collection of edges (e1; e2; : : : ; ek) such that one can reach v0 from v by successively traversing e1; : : : ; ek in the speci ed order. Following [Tal12], let us recall the following de nitions. The weight of a given path P = (e1; : : : ; ek) is: where A = (Aij ) is the weighted adjacency matrix of the graph (Aij = wij if there is an edge from vi to vj , and 0 otherwise).
A cycle is a path from a vertex v to itself (or more precisely an equivalent class thereof up to change of source vertex). We denote by C the set of all possible collections of self-avoiding and pairwise vertex-disjoint cycles, including the empty collection. Given C = (C1; : : : ; Ck) 2 C, we de ne its weight and sign as wt(C) := k Y wt(Ci) ; i=1 and sgn(C) := ( 1)k; while, by convention, wt(C) = sgn(C) = 1 for the empty collection.
Lemma 2.1. The determinant of M 1 is: det(M 1) =
X sgn(C):wt(C): (10) (11) (12) (13) (14) (15) (16) (17) The weight path matrix of the graph G is the matrix M = (mij )1 i;j N , whose entries are:
These quantities are considered as formal power-series in the weights. A crucial remark is that
0
N X i;j=1 det(M 1) =
Z i( ij
Aij ) j A =
d d Z 3See, for example, [FKT02], for more details on Grassmann integration and Grassmann changes of variables. wt(P ) := m Y wek : k=1 mij :=
X wt(P ): M = (Id
A) 1; C2C
1
giving a non-zero contribution to the integral if and only if: all Grassmann variables appear exactly once and Akjlj 6= 0 for all 1 j s. Let us assume that this is the case. The inequality Akjlj 6= 0 implies that there is a directed edge ej from vkj to vlj ; this means that Akjlj = wkjlj . Let us call Hs the subgraph made out of the edges e1; : : : ; es. Each ingoing (resp. outgoing) edge at a vertex v` 2 Hs is associated to a variable ` (resp. `). Hence there cannot be more than one ingoing (resp. outgoing) edge of Hs at each v`. On the other hand, if there were only say one ingoing but no outgoing edge at v`, this would require that ik = ` for some 1 k r. This would however necessarily bring a second factor ik and therefore cancel the integrand. We conclude that there must be exactly one ingoing at one outgoing edge at each vertex of Hs. This means that Hs must decompose into a collection C of self-avoiding and pairwise vertex-distinct cycles. Furthermore there is in this case a unique choice of indices 1 i1 < : : : < ir N yielding a non-vanishing monomial of degree 2N . Each collection of cycles C is weighted by wt(C), up to a sign. Moreover, the integral is of the form of (7), with a product of jCj disjoint cycles of even length, the other cycles being trivially of length 1. The signature of is therefore sgn(C), and we conclude that C contributes with a term sgn(C)wt(C).
One considers now the minor MAB, where A = fa1; : : : ; apg and B = fa1; : : : ; apg are p-dimensional sets of indices in f1; : : : ; ng. A p-path from A to B is a collection of paths P = (P1; : : : ; Pk) s. t. Pi connects ai to b P(i), for some permutation P. The weight and sign of P are furthermore given by: k Y wt(Pi) ; i=1 wt(P) := and sgn(P) := sgn( P): The p-path P is self-avoiding if: 1) each Pi is self-avoiding; 2) Pi and Pj are vertex-disjoint whenever i 6= j.
Finally, a self-avoiding ow from A to B is a pair (P; C) such that: 1) P 2 PA;B; 2) C 2 C; and 3) P and C are vertex disjoint. We denote the set of self-avoiding ow from A to B by FA;B.
Theorem 2.2. One has [Tal12] In particular, if G is acyclic then [GV85, Lin73]: det(MAB) =
P (P;C)2FA;B sgn(P)wt(P) sgn(C)wt(C) P sgn(C)wt(C) C2C : det(MAB) =
sgn(P)wt(P):
X P2PA;B
Proof. The left-hand side of (20) is a minor of the matrix M . We need to re-express it as a minor of M 1. To this purpose, we could directly use det((M 1)AB) = ( 1) A+ B detd(eMt(BMc A)c ) . Nevertheless, in this paper we instead rely exclusively on Grassmann calculus. One can thus use formula (9) to express det(MAB) as
N X i;j=1
1 (19) (20) (21) (22) (23) The denominator is given by Lemma 2.1. The integral in the numerator writes: k;`=1 1
Z kMk`1 `A d d
Bc Ac exp
! X( k k + k k) : k
Lemma 2.3. The following identity holds
Z d d
Bc Ac exp
N X( k k + k k) k=1 ! = ( 1) A+ B
B A: Proof. When developing the exponential in (25) above, the only term which leads to a non-vanishing contribution is the one containing: The Grassmann integration on the lef-hand side of (25) leads to ( A B) multiplied by the sign: (24) (25) (26) (27) (28) (29) !
Z p Y i=1 ai ai
bi bi p Y i=1 !
p = Y i=1
ai ai bi bi = ( B A)( B A): d d ( Bc Ac ) ( B A) = ( 1) A+ B:
Z d d
Z d d
B A
N N Y e i i Y i=1 k;`=1 e kAk` ` : ( 1)p
Z d d
B A A similar analysis as the one of Lemma 2.1 then shows that the non-zero contributions to the integral are labelled by self-avoiding ows (P; C) 2 FA;B. Indeed, open paths are now allowed, but their source (resp. sink) vertices must be associated to a Grassmann variable ai (resp. bi ) and therefore be in A (resp. in B). The key argument is that, because of the Grassmann nilpotency condition (2), the paths and cycles must be self-avoiding and pairwise vertex-disjoint!
The term indexed by the ow (P; C) is equal to wt(P) wt(C), up to a sign. By the same argument as in Lemma 2.1, the term associated to (P; C) di ers from the one associated to (0; ;) by a factor sgn(C). In the latter situation, one can relabel the variables bi and assume without loss of generality that Pi connects ai to bi (for all i), and that a factor sgn(P) is included. The only di erence with respect to the case studied in Lemma 2.1 is that we have now a permutation with jPj = p even cycles, yielding an extra factor ( 1)p which cancels the one of formula (29). Finally, the sign associated to a general (P; C) 2 PAB is equal to sgn(C)sgn(P), which concludes the proof. 3
Transfer matrix approach In quantum eld theory, the path integral represents a space time approach to the time evolution of a system, represented as a sum over paths. Accordingly, the LGV lemma is interpreted as the evolution of a system of fermions on a lattice that represents a discrete analogue of space-time. In some instances, it turns out that this evolution can also be described in another formalism based on singling out a time direction in space-time. In our case, this formalism applies to a particular class of graphs which are described below. The sum over paths 1.a. Graph G1 ! G2 ! ! Gn
Let us consider N Grassmann variables 1; : : : ; N . The scalar product is de ned in analogy with the standard scalar product on holomorphic functions, using an integration over Grassmann variables
Z hf; gi =
T~ f ( ) = XN 1 k! k=0 1 i1;:::;ik N
X ai1:::ik
X 1 j1 N
T~i1j1 j1 ) : : :
X 1 jk N
T~ikjk jk : Z T~ f ( ) =
T
N = X i;j=1
~ iTij j : G2 G1 (30) (31) (32) (33) (34) (-3,4) 3 Consider now a sequence of n weighted directed graphs G1; : : : ; Gn each having N vertices labeled by an integer i 2 f1; : : : ; N g. Loops, multiple edges and isolated vertices are allowed. We denote by wm;ij the weight of an edge oriented from vertex i to vertex j in Gm, with the convention that the weight vanishes if there is no such an edge. We label the nN vertices of the disjoint union G1 [ [ Gn by pairs (i; m) where the second index refers to the graph Gm and the rst one to the vertex i in Gm.
We de ne the graph G1 ! G2 ! ! Gn by adding N (n 1) edges to the disjoint union G1 [ [ Gn see Fig. 1.a. These N (n 1) edges connect the vertex (i; m) to the vertex (i; m + 1), for all m 2 f1; : : : ; n 1g and i 2 f1; : : : ; N g with a weight 1. The weighted adjacency matrix of G1 ! G2 ! ! Gn is given by A(i;m);(j;p) := >8wi;j if p = m <
1 if p = m + 1 and i = j >:0 otherwise:
The previous construction is motivated by the following theorem, relating k non intersecting paths in G1 ! G2 ! ! Gn, starting at vertices A 2 G1 and ending at vertices B 2 Gn, to a k k minor in a N N matrix constructed using the weighted adjacency matrices Ai of Gi. Theorem 3.1. One has
X non intersecting paths P1; : : : ; Pk A ! B and cycles C1; : : : ; Cr in G1 ! G2 ! ! Gn ( 1) (A;B)( 1)rw(P1) w(Pk)w(C1)
w(Cr) = det(1
An) det(1
A1) det (1 (1
A1) 1
AB ; (35) with (A; B) the signature of the permutation of the labels of the vertices in B with respect to those in A and det MA;B is the determinant restricted to the lines corresponding to A and columns to B.
Proof. The result is proved by induction on n. For n = 1, the statement corresponds to Theorem 2.2. Then, one passes from n to n + 1 by integrating pairs of variables between vertices (i; m) and (i; m + 1) and the use of (33).
In statistical physics, a homogeneous term of degree k in H represents a state of k fermions occupying the vertices of Gm at time m. The anti-commutation relations express Pauli exclusion principle that states that two fermions cannot occupy the same vertex. The operator (1 Am) 1 (multiplied by a power of its determinant) transforms this state into another k fermion state at time m + 1, on the vertices of Gm+1. Thus, Tm represents a discrete time evolution; this matrix is known in physics as the transfer matrix.
The interest of this result comes from the evaluation of the sum over paths by a minor in an N N matrix instead of an nN nN matrix as would result from an application of the LGV lemma. In the next two sections we show how this result can be used in the theory of Schur functions. Other related applications of fermionic techniques can be found in [LLN09] and [Zin09]. 4
An application to Schur functions Given an integer k, a partition of k is a decreasing sequence 1 r of r integers such that 1 + + r = k. A partition is conveniently represented by a Young diagram denoted and made of r left justi ed rows, the kth row containing k boxes, with the longer rows on the top of the shorter ones. We set j j := 1 + + r.
Given a second Young diagram with r0 rows, we write if r0 r and if for all i f1; : : : ; rg, i i. When , the skew Young diagram = is constructed by removing the i rst left boxes in the line i of for all i. We also consider the empty Young diagram and =; = while = = ;. We further set i = 0 for i r0.
A semi standard (skew) Young tableau (SSYT) of shape = is a lling of the Young diagram = by some integers in f1; : : : ; ng in such a way that they are increasing along the columns and non decreasing along the rows. To each of these integers we associate an indeterminate xm and the Schur function is de ned as s = (x) :=
X
Y
xkmm ; skewoYfoshuanpgeTableau 1 m n = where km is number of times the integer m appears in the SSYT, see Fig. 1.c.
It is known (see [GV85]) that s = (x) can be constructed using r non intersecting lattice paths as follows. De ne a graph G with vertices labelled (i; m) with i and m positive integers and oriented edges from (i; m) to (i + 1; m) and from (i; m) to (i; m + 1). The graph G is conveniently visualized as a two dimensional square lattice with arrows pointing upwards and rightwards. Although in nite, at any stage of the computation only a nite number of vertices are involved. We leave the precise range of i unspeci ed for notational convenience and assume 1 m n unless otherwise stated. Then, the skew Schur functions can be written as a sum over r non intersecting paths on G, s (x) =
X non intersecting lattice paths P1; : : : ; Pr
Pi: ( i i+l;1)!( i i+l;n)
W (P1)
W (Pi): where l is a global translation parameter that does not a ect the result, because of translation invariance. The weight of a path is again given by the product of the weight of its edges. The weight of an horizontal edge from (i; m) to (i + 1; m) is xm and the weight of all vertical edges is 1.
The graph G can be written as G = G1 ! G2 ! ! Gn with all Gm isomorphic to a one dimensional lattice with edges oriented to the right, i.e. from i to i + 1. The weighted adjacency matrix is made of right translations T (de ned by Tij = 1 if j = i + 1 and 0 otherwise) multiplied by xm, such that 1 Its inverse reads (1 Am) 1 = Pp 0(xm)p T p. One then has xmT . with hk(x) the complete symmetric functions of x1; : : : ; xn of degree k, (1 (1
A1) 1 = X hk(x)T k;
k hk(x) =
X then leads to the convolution identity: h jU (x)j i =
X h jU (x0)j ih jU (x00)j i s = (x) =
X s = (x0)s = (x00): U a(x) = X Sk(a; x)T k; (38) (39) (40) (41) (42) (43) (44) (45) (46) This identity follows from the LGV lemma. From a lattice point of view, this is a vertical composition. In the next section, we will derive an horizontal composition from the multiplication law
U a+b(x) = U a(x)U b(x): 5
A one parameter extension of Schur polynomials
Sk(a; x) =
X k1+ kn=k x1k1 : : : xknn
Y 1 m n a(a + 1) : : : (a + km 1)
: km! For a = 1 we recover the complete homogeneous polynomials Sk(1; x) = hk(x). For example, S1(a; x) = a X
xm; 1 m n S3(a; x) =
S2(a; x) = a(a + 1) X 2 1 m n x2m + a2
X These polynomials appear in the expansion of U a(x) = (1 xnT ) a (1 x1T ) a, generalizing (38), which follows from writing (1 xmT ) a = (1a) R01 dtmtam 1 exp tm(1 xmT ). Using U a(x) = (1 xnT ) a (1 x1T ) a in equation (35) instead of U (x) = (1 xnT ) 1 (1 x1T ) 1 leads to a one parameter generalization of the Schur function. The latter are de ned by replacing the hk(x) by Sk(a; x) in the Jacobi-Trudi identity (40).
s = (a; x) := det S j i+i j (a; x) 1 i;j r: We use here the convention S0(a; x) = 1 and Sk(a; x) = 0 for k < 0.
Schur functions are recovered for a = 1, s = (1; x) = s = (x). Theorem 3.1 then implies that S = can also be written as a sum over r non intersecting lattice paths for a skew diagram with r rows. However, since we use (1 xmT )a instead of (1 xmT ), for j > i there is an edge from (i; m) to (j; m) weighted by w(i;m)!(j;m) = ( 1)j i+1 a(a 1) : : : (a (j i)! j + i + 1) xjm i: In that case, the paths (i; m) ! (i; p) ! (j; p) ! (j; q) and (k; m) ! (k; q) for i < k < j do not intersect but contribute with an extra 1 because the order of their endpoints have been reversed.
Example 5.2 (s(2;1)(a; x) as a sum over paths). The paths contributing to s(2;1)(a; x) join vertices (1; 1) and (2; 1) on on side and (2; n) and (4; n) on the other side.
The result then follows from the expansion of the determinant in (47), expansion which uses the Cauchy-Binet formula.
s (a + b; x) = s (a; x) + s (a)s (b)(x) + s (a; x)s (b; x) + s (a; x)s (b; x) + s (b; x): (52)
Other identities satis ed by s (a; x) can easily be proven. For example, for the conjugate diagrams (obtained by symmetry with respect to the main diagonal), one has:
s = (a; x) = ( 1)j j j js = ( a; x): For Schur functions, the last three contributions are absent (a = 1), since they involve horizontal segments of length 2 and 3. In the last two rows there is a extra sign because of the interchange of endpoints. s (a; x) = det
S2(a; x) S3(a; x)
1 S2(a; x) = a(a2
1) 3
X 1 m n x3m + a2 X xmxpxq: 11 pp< mq nn
The main interest of this extension of Schur polynomials is the following convolution identity:
Note that, for the empty partition, one has: s;(a; x) = 1.
Proof. The proof relies on the multiplication law U a(x)U b(x) = U a+b(x). This translates to s = (a + b; x) =
s = (a; x)s = (b; x):: Sk(a + b; x) =
X Sp(a; x)Sq(b; x): (1; 1) ! (1; m) ! (2; m) ! (2; n) (2; 1) ! (2; p) ! (3; p) ! (3; q) ! (4; q) ! (4; n) (1; 1) ! (1; m) ! (2; m) ! (2; n) (2; 1) ! (2; p) ! (4; p) ! (4; n) (1; 1) ! (1; m) ! (4; m) ! (4; n)
(2; 1) ! (2; n) (1; 1) ! (1; m) ! (3; m) ! (3; p) ! (4; p) ! (4; n) (2; 1) ! (2; n) a3
X 11 pp<mq nn; a2(a
1) 2 2 a(a + a2(a 1)(a 6 1)
xmxpxq (47) (48) (49) (50) (51) TK and AT are partially supported by the grant ANR JCJC \CombPhysMat2Tens". AT is partially supported by the grant PN 16 42 01 01/2016. SC is supported by the grant ANR JCJC \CombPhysMat2Tens". AT thanks
[Tal12] K. Talaska. Determinants of weighted path matrices. At https://arxiv.org/abs/1202.3128.