# Computational complexity of symbolic determinant

I'm using the Det function in Mathematica to compute the determinant of an $n\times n$ matrix $A$ with entries of the form $a+bt$ with $a,b$ integers and $t$ a variable, and I would like to know what the computational complexity of this function is. For a non-symbolic matrix one can find its determinant in time $O(n^3)$ by Gaussian elimination, but it seems to be more expensive to compute the determinant of my matrix $A$. Does someone know how expensive?

## 1 Answer

I get a better fit with an asymptotic complexity between n^4 and n^5. I think Det is doing a lot of simplification of symbolic expressions, which may account for some of the increased complexity.

nMax = 35;
entry[] := RandomInteger[{-9, 9}] + RandomInteger[{-9, 9}]*t
findTime[n_] := Block[{m, time, det},
m = Table[entry[], {i, 1, n}, {j, 1, n}];
{time, det} = Timing[Det[m]];
Return[{n, time}]
]
timingData = findTime /@ Range[nMax];

curve = Fit[timingData, x^4.5, x];
Show[ListPlot[timingData], Plot[curve, {x, 0, nMax}]]


Contrast this with floating-point matrix determinants, which nicely follow the x^3 asymptotic complexity:

nMax = 4000;
nSkip = 100;
findTime[n_] := Block[{m, time, det},
m = RandomReal[{-9, 9}, {n, n}];
{time, det} = Timing[Det[m]];
Return[{n, time}]
]
timingData = findTime /@ Range[1, nMax + 1, nSkip];

curve = Fit[timingData, x^3, x];
Show[ListPlot[timingData], Plot[curve, {x, 0, nMax}]]

• Thanks! Do you know where to find what Det exactly does?
– Sof
Jul 24, 2014 at 17:51
• Documentation Center page tutorial/SomeNotesOnInternalImplementation#7441 says, "Det uses direct cofactor expansion for small matrices and Gaussian elimination for larger ones." Jul 24, 2014 at 18:23
• Is it possible to argue theoretically that it can be bounded by $O(n^5)$? I don't know how to use the fact that the entries contain a variable t and not just floating points..
– Sof
Jul 25, 2014 at 16:51
• I think best possible is O(n^4) or possibly better with asymptoticvally fast matrix multiplication. Also there will be a factor to account for integer coefficient size. For a practical approach you might try doing it by explicit polynomial interpolation. Jul 27, 2014 at 1:32