Aarhus University Seal / Aarhus Universitets segl

On the Determinantal Complexity of the 2-hook-immanant

by Uffe Heide-Jørgensen
PhD Dissertations | September 2012

A result by Leslie Valiant states that any polynomial can be written as the determinant of a square matrix with affine entries, i.e., entries that are polynomials of degree at most 1. Given a polynomial, $p$, the determinantal complexity of $p$ is defined to be the smallest integer, $n$, such that $p=\det\nolimits_nM$ where $M$ is some $n\times n$-matrix with affine entries.

In this thesis the subject of determinantal complexity is investigated, and a quadratic lower bound of the determinantal complexity of the family of polynomials known as the 2-hook-immanants is shown.

Format available: PDF (532 KB)
Thesis advisor: Niels Lauritzen