2
$\begingroup$

In general determinants have many identities. Would it help the $GCT$ program by invoking the paradigm of identities such as to state that if the permanent is converted to determinant then it has to satisfy certain identities and therefore by reason $x,y,z$ we get lower bound on permanent or does it reduce to the symmetry characterization also (simply because determinantal identities follow from symmetries)? I am asking this because may be there are identities (I cannot think of one) that need only fewer essential symmetries (other symmetries just follow as consequence) making it easier to prove lower bounds (any superpolynomial lower bound on weaker assumptions can only be good).

$\endgroup$
  • $\begingroup$ Why the downvote? $\endgroup$ – Joshua Grochow Jul 19 '17 at 14:16
5
$\begingroup$

Determinantal identities can be useful, but perhaps not exactly in the way you think. As far as I know, however, the identities do not all "reduce to" the symmetries of the determinant (except for the fact that the symmetries of the determinant characterize it). Whenever one has some determinantal identities, they can often be massaged into getting equations for the orbit closure of the determinant - the closure of the set of homogeneous polynomials that are linear projections of the determinant. The family of these orbit closures (one for each size $n$) is a natural geometric object capturing the complexity class $\mathsf{VP}_{s}$.

Some work in this direction by Landsberg & Ressayre was reported here (Section 2.2), but I don't know if the actual paper has appeared yet.

A somewhat related paper, which gives some equations that vanish on the determinant orbit closure is:

Landsberg, Manivel, & Ressayre. Hypersurfaces with degenerate duals and the Geometric Complexity Theory program. Comentarii Mathematici Helvetici 88(2):469-484, 2013. (arXiv version)

That paper, as with Mignon-Ressayre, uses the rank of the Hessian, rather than explicitly from a determinantal identity. However, the rank of the Hessian can be seen as closely related to Segre's identity $\det_{n^2}(Hess(\det_n(A)) = (-1)^{\binom{n+1}{2}}(n-1)\det(A)^{n(n-2)}$, which is the identity reportedly used above.

You might also be interested in the following paper, which shows that any reduction from perm to det which respects the symmetries of perm (see the paper for precise definitions) must have exponential blow-up:

J. M. Landsberg and Nicolas Ressayre. Permanent v. determinant: an exponential lower bound assumingsymmetry and a potential path towards Valiant's conjecture. Differential Geom. Appl., in press, 2017. (arXiv version)

$\endgroup$
  • $\begingroup$ sorry to bother but do you know any compendium of identities shared both by permanent and determinant because as you say not all symmetries need to be used by determinant identities and permanent pretty much has no interesting symmetries and so may be there are some identities that work for both permanent and determinant? $\endgroup$ – T.... Jul 20 '17 at 10:36
  • $\begingroup$ any identities at all? $\endgroup$ – T.... Jul 20 '17 at 11:14
  • $\begingroup$ @AJ.: perm has enough symmetries to be characterized by them, so that seems pretty interesting to me. Identities and symmetries are related but not equivalent. There's a whole literature out there on determinantal and permanental equalities and inequalities. $\endgroup$ – Joshua Grochow Jul 20 '17 at 14:24
  • $\begingroup$ I see can you provide one reference and I can dig literature? $\endgroup$ – T.... Jul 20 '17 at 15:07
  • $\begingroup$ one reference where an identity holds for both permanent and determinant. $\endgroup$ – T.... Jul 20 '17 at 15:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.