Computational complexity of computing the determinant

The most important property of the determinant is that it's multiplicative, which is what makes row reduction work. (Note that the permanent isn't.) This is not a trivial consequence of the permutation expansion of the determinant; working from the permutation expansion one can deduce multiplicativity combinatorially but it is, in my opinion, more work than necessary.

Really this multiplicativity is about functoriality: the determinant is just the action of the exterior power functor $\Lambda^n(-)$ on endomorphisms $T : V \to V$ of $n$-dimensional vector spaces. Again, the permanent doesn't arise in this way. There is extra structure here and it isn't trivially deducible from the permutation expansion but requires some actual thought about where the determinant comes from and why people care about it in the first place.

Actually the computation of the determinant of a matrix is not bounded by a polynomial in the dimension of the matrix and size of the entries. Try calculating the determinant of an $n\times n$ matrix with $n^2$ distinct indeterminates as entries (in a polynomial ring or field of rational functions in that many indeterminates); the result has $n!$ terms. Gaussian elimination only works over a field, but as the example shows even then it is not reasonable to assume constant-time arithmetic without more information. In fact the $O(n^3)$ estimate is only realistic over finite fields.