Skip to main content
11 votes
Accepted

The minimum number of arithmetic operations to compute the determinant

It is known that the number of arithmetic operations necessary to compute the determinant of an $n\times n$ matrix is $n^{\omega+o(1)}$, where $\omega$ is the matrix multiplication constant. See for ...
A. Rex's user avatar
  • 276
11 votes
Accepted

Maximum Polyhedron Volume in Given $n$ Points

This was shown to be hard (more precisely $\mathsf{NP}$-hard to approximate to better than exponential in $k$) by Marco Di Summa, Friedrich Eisenbrand, Yuri Faenza, Carsten Moldenhauer, "On largest ...
David Eppstein's user avatar
9 votes
Accepted

Complexity of computing generalised determinants. (P - #P transition)

I extend my comment in an answer. By rewriting $e^{i \cdot sgn(\mu)\theta} = \cos(sgn(\mu)\theta)+i\sin(sgn(\mu)\theta) = \cos(\theta)+i \cdot sgn(\mu)\sin(\theta)$ we have: $Det_\theta(A) = \cos(\...
holf's user avatar
  • 2,174
6 votes
Accepted

Complexity of $\{0,\pm1\}$ determinant in sparse cases?

Depends how you feel about the exponent of matrix multiplication, as this would come very close to showing $\omega=2$. If the answer to your question were positive, then you could compute the ...
Joshua Grochow's user avatar
6 votes

How many multiplications are needed to compute the determinant of a 3×3 matrix?

I have a partial answer to this now. I still don’t know whether anyone had ever explicitly written down a method for computing the 3×3 determinant using 8 multiplications, but anyone with sufficient ...
Robin Houston's user avatar
5 votes
Accepted

Application of weak determinantal identities to GCT?

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 ...
Joshua Grochow's user avatar
5 votes
Accepted

Can a sum of polynomially many determinants be expressed as a single determinant of a poly-size matrix?

It is possible and proven in [1, Proposition 7]. More precisely, Malod and Portier show that the determinant is linearly closed, that is, every linear combination of the form $\sum_{i=1}^n \lambda_i ...
holf's user avatar
  • 2,174
3 votes

Coefficients of a determinant of a matrix of univariate polynomials is in $GapL$

Theorem 3.2 in this paper: https://doi.org/10.1007/s00224-003-1077-7 says this: Let B be an n × n matrix, whose entries are each polynomials of degree n in Z[x], where the coefficients of each ...
Eric Allender's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible