restart:with(LinearAlgebra):Truncated power series and linear algebra (naive implementations here)Application to elimination of divisions Also see "On the complexity of computing determinants", 2005 Gaussian elimination with divisionsGaussdiv:=proc(A,x) local i,j,k,n,M,MM,p; n:=RowDimension(A); MM:=Vector(n): M:=copy(A); for i from 1 to n-1 do p:=1/M[i,i]: for j from i to n do MM[j]:=M[i,j]*p: od: for k from i+1 to n do p:=M[k,i]: for j from i to n do M[k,j]:=M[k,j]-p*MM[j]: od: od: od: return(M);end:n:=4;A:=RandomMatrix(n,n);G:=Gaussdiv(A);delta:=G[1,1]: for i from 2 to n do delta:=delta*G[i,i]: od: delta;Determinant(A); Inversion of power series using multiplications only (Newton)inv:= proc(f,x,m) local k,i,g,t; # Power series of the type 1 + xw k:=ceil(log[2](m)); g:=1; for i from 1 to k do g:= rem(g+(1-g*f)*g,x^(2^i),x): od: return(sort(rem(g,x^m,x),x,ascending));end:n:=8;f:=sort(expand(1+x*randpoly(x,degree=n,dense)),x,ascending);m:=n+1;g:=inv(f,x,m);sort(rem(f*g,x^(m+2),x),x,ascending); Gaussian elimination over truncated power series Gaussnodiv:=proc(A,x,m) local i,j,k,n,M,MM,p; n:=RowDimension(A); MM:=Vector(n): M:=copy(A); for i from 1 to n-1 do p:=inv(M[i,i],x,m): for j from i to n do MM[j]:=rem(M[i,j]*p,x^(m),x): od: for k from i+1 to n do p:=M[k,i]: for j from i to n do M[k,j]:=rem(M[k,j]-p*MM[j],x^(m),x): od: od: od: return(M);end:n:=4;A:=RandomMatrix(n,n); Homotopy M:=1+x*(A-1);m:=2;G:=Gaussnodiv(M,x,m); Approximation of the polynomial determinantdelta:=G[1,1]: for i from 2 to n do delta:=rem(delta*G[i,i],x^m,x): od: delta;Determinant(M);m:=n+1;G:=Gaussnodiv(M,x,m); Approximation of the polynomial determinant (sufficient order)delta:=G[1,1]: for i from 2 to n do delta:=rem(delta*G[i,i],x^(m+4),x): od: sort(delta,x,ascending); that gives the determinant (the order of the approximation is large enough) delta:=G[1,1]: for i from 2 to n do delta:=rem(delta*G[i,i],x^m,x): od: sort(delta,x,ascending);subs(x=1,delta);Determinant(A); Note on the characteristic polynomialA;CharacteristicPolynomial(A,x);Determinant(x-A);M:=1-x*A;G:=Gaussnodiv(M,x,m);delta:=G[1,1]: for i from 2 to n do delta:=rem(delta*G[i,i],x^m,x): od: delta;CharacteristicPolynomial(A,x);____________________________________________________