Search code examples
algorithmpolynomialsdeterminants

Is there a fast algorithm for determinant of matrix filled with variables?

I am desperately searching for a polynomial time algorithm, that computes the determinant of a symbolic (n x n) matrix.

The problem is, that each entry of the upper triangular half of the matrix consists of a different variable (e.g. x_1, x_2, ...).

On the diagonal, each entry is a polynomial that consists of the negative sum of up to (n-1) of these variables (e.g. (- x_1 - x_2 - x_3), (- x_3 - x_2), ...).

However it is always a symmetric matrix, so the entries are the same if you mirror them along the diagonal. Maybe this property helps with the runtime?

I have already considered the LU-Decomposition algorithm, but I am afraid it only works for purely numerical matrices, or am I wrong?

Could someone please help me out here?

Solution

  • @MattTimmermans comment answers the question:

    "LU (not LUP) decomposition works fine symbolically. Every cell contains a rational function, and the set of rational functions is closed over all the required operations ( *, /, +, -)"

    This seems to mean that I can use the LU decomposition algorithm as is, but whenever the LU decomposition algorithm uses one of these operators, this operator has to be implemented for polynomials as a subfunction.

    Thanks a lot!