# Bottom up minor expansion
# Reference: Morven Gentlman and Stephen Johnson
#   Analysis of Algorithms, A Case Study:
#   Determinants of Matrices With Polynomial Entries
#   Trans. on Math. Soft. (TOMS) 2(3):232-241, ACM, 1976
# Copyright, Michael Monagan, 2022

detbot := proc(A::Matrix,n::posint) local i,j,S,R,c,t,T,d;
    for i to n do T[[i]] := A[i,n] od;
    S := [seq([i],i=1..n)];
    for i from 2 to n do
        R := combinat[choose](n,i);
        for c in R do
            d := 0;
            for j to nops(c) do
                t := (-1)^(j-1)*A[c[j],n-i+1];
                d := d + expand( t*T[subsop(j=NULL,c)] );
            od;
            T[c] := d;
        od;
        for c in S do T[c] := evaln(T[c]) od; # remove these from T
        S := R;
    od;
    d := T[[seq(i,i=1..n)]];
end:


# Test
with(LinearAlgebra):
A := Matrix([[1,u,u^2],[1,v,v^2],[1,w,w^2]]);
detbot(A,3) - Determinant(A);
T := ToeplitzMatrix([t,u,v,w,x,y,z,y,x,w,v,u,t],shape=symmetric);
detbot(T,7) - Determinant(T);
T := ToeplitzMatrix([s,t,u,v,w,x,y,z,y,x,w,v,u,t,s],shape=symmetric);
detbot(T,8) - Determinant(T);