On the Determinantal Complexity of the 2-hook-immanant

By Uffe Heide-Jørgensen
PhD Dissertations
September 2012
Abstract:

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.

Thesis advisor: Niels Lauritzen
Format available: PDF (544.5 kb)