【线性代数】行列式的概念

$$det(A)=\sum _{i_1,i_2,\cdots ,i_n}(-1{)}^{\sigma (i_1,\cdots ,i_n)}{a}_{1,i_1}{a}_{2,i_2},\cdots ,a_{n,i_n}$$

$i_1,\cdots ,i_n$ 是 $1,\cdots ,n$ 的排列.

计算复杂度

$$O(n\cdot n!)$$

{ 1 , 2 } \{1,2\} {1,2} 的全排列如下

$$\left[\begin{array}{cc}{a}_{1,1}& a_{1,2}\\ a_{2,1}& a_{2,2}\end{array}\right]$$

{ 1 , 2 , 3 } \{1,2,3\} {1,2,3} 的全排列如下

$$\left[\begin{array}{ccc}{a}_{1,1}& a_{1,2}& a_{1,3}\\ a_{2,1}& a_{2,2}& a_{2,3}\\ a_{3,1}& a_{3,2}& a_{3,3}\end{array}\right]$$

递归法生成全排列

using CSV, DataFrames, Tables
function OE(sigma)   # 判断奇偶置换n=length(sigma); out=1for i=1:nfor j=1:n-1if sigma[j] > sigma[j+1]out=-out;  sigma[j],sigma[j+1]=sigma[j+1], sigma[j]endendendreturn(out)
end
function remove_last(seq)   # 删除序列最后一个元素
lth=length(seq)
z=copy(seq[1:lth-1])
return(z)
end
function rankfull(seq,n,cpl)  # 递归全排列生成器lth=length(seq)if lth==1m=[cpl; seq]open("rankfull_sol.txt","a") do iofor i=1:ns=m[i];  write(io, "$s,")endwrite(io,"\n");endelsefor i=1:lths=seq[i];    idx=0;list=zeros(Int,lth-1)for j=1:lthif !(seq[j]==s)idx=idx+1;  list[idx]=seq[j]endendcpl=[cpl; s];rankfull(list,n,cpl)cpl=remove_last(cpl)endend
end
function det_defn(A)  # 定义法求行列式lth=size(A,1)seq=1:lthglobal ranksol=[seq];lth=length(seq); cpl=[]; iters=factorial(lth)tryrankfull(seq,lth,cpl)catch nothingendio=open("rankfull_sol.txt","r")data=read(io,String)file = CSV.File(IOBuffer(data), header=false)CSV.write("fullrank.csv", file)close(io)sigma=zeros(Int64,iters,lth);for i=1:factorial(lth)for j=1:lthsigma[i,j]=file[i][j]endendDETs=0*A[1,1]for i=1:itersPrs=1for j=1:lthPrs=Prs*M[j,sigma[i,j]]endDETs=DETs+ OE(sigma[i,:])*Prsendreturn(DETs)
end
M=[4//1 3 2 1;3 2 1 4;2 1 4 3;1 4 3 2]
a= det_defn(M)
println("\n")
println("defn=",a)

-160//1

邻近对换算法生成全排列

function ranking(lth)  # 邻近对换全排列生成器prd=1;  arr=zeros(Int64,lth);for i=1:lth arr[i]=i endfor i=1:lth   prd=prd*i endjx=lth  ; dr=-1;   s=0;for j=1:prdif dr<0if jx>1arr[jx],arr[jx+dr] =   arr[jx+dr],arr[jx]jx=jx+drelsearr[lth],arr[lth-1] =   arr[lth-1],arr[lth]dr=-drendelseif jx<ltharr[jx],arr[jx+dr] =   arr[jx+dr],arr[jx];jx=jx+drelsearr[1],arr[2] =   arr[2],arr[1];   dr=-drendendopen("ranking_sol.txt","a") do iofor i=1:lths=arr[i];  write(io, "$s,")endwrite(io,"\n");end    end
end
function det_defn2(A)  # 定义法求行列式lth=size(A,1)seq=1:lthglobal ranksol=[seq];lth=length(seq); cpl=[]; iters=factorial(lth)try rm("ranking_sol.txt")catchnothingendranking(lth)io=open("ranking_sol.txt","r")data=read(io,String)file = CSV.File(IOBuffer(data), header=false)CSV.write("fullrank.csv", file)close(io)sigma=zeros(Int64,iters,lth);for i=1:factorial(lth)for j=1:lthsigma[i,j]=file[i][j]endendDETs=0*A[1,1]for i=1:itersPrs=1for j=1:lthPrs=Prs*M[j,sigma[i,j]]endDETs=DETs+ OE(sigma[i,:])*Prsendreturn(DETs)
end    
M=[4//1 3 2 ;3 2 1 ;2 1 4]
a= det_defn2(M)

-160//1