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

$$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=1
   for i=1:n
      for j=1:n-1
         if sigma[j] > sigma[j+1]
            out=-out;  sigma[j],sigma[j+1]=sigma[j+1], sigma[j]
         end
      end
   end
   return(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==1
      m=[cpl; seq]
      open("rankfull_sol.txt","a") do io
          for i=1:n
              s=m[i];  write(io, "$s,")
          end
          write(io,"\n");
      end
   else
      for i=1:lth
         s=seq[i];    idx=0;
         list=zeros(Int,lth-1)
         for j=1:lth
            if !(seq[j]==s)
               idx=idx+1;  list[idx]=seq[j]
            end
         end
         cpl=[cpl; s];
         rankfull(list,n,cpl)
         cpl=remove_last(cpl)
      end
   end
end
function det_defn(A)  # 定义法求行列式
   lth=size(A,1)
   seq=1:lth
   global ranksol=[seq];
   lth=length(seq); cpl=[]; iters=factorial(lth)
   try
       rankfull(seq,lth,cpl)
   catch nothing
   end
   io=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:lth
          sigma[i,j]=file[i][j]
       end
   end
   DETs=0*A[1,1]
   for i=1:iters
      Prs=1
      for j=1:lth
         Prs=Prs*M[j,sigma[i,j]]
      end
      DETs=DETs+ OE(sigma[i,:])*Prs
   end
   return(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 end
    for i=1:lth   prd=prd*i end
    jx=lth  ; dr=-1;   s=0;
    for j=1:prd
        if dr<0
            if jx>1
                arr[jx],arr[jx+dr] =   arr[jx+dr],arr[jx]
                jx=jx+dr
            else
                arr[lth],arr[lth-1] =   arr[lth-1],arr[lth]
                dr=-dr
            end
        else
            if jx<lth
                arr[jx],arr[jx+dr] =   arr[jx+dr],arr[jx];
                jx=jx+dr
            else
                arr[1],arr[2] =   arr[2],arr[1];   dr=-dr
            end
        end
        open("ranking_sol.txt","a") do io
            for i=1:lth
                s=arr[i];  write(io, "$s,")
            end
            write(io,"\n");
        end    
    end
end
function det_defn2(A)  # 定义法求行列式
   lth=size(A,1)
   seq=1:lth
   global ranksol=[seq];
   lth=length(seq); cpl=[]; iters=factorial(lth)
   try rm("ranking_sol.txt")
    catch
        nothing
   end
   ranking(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:lth
          sigma[i,j]=file[i][j]
       end
   end
   DETs=0*A[1,1]
   for i=1:iters
      Prs=1
      for j=1:lth
         Prs=Prs*M[j,sigma[i,j]]
      end
      DETs=DETs+ OE(sigma[i,:])*Prs
   end
   return(DETs)
end    
M=[4//1 3 2 ;
   3 2 1 ;
   2 1 4]
a= det_defn2(M)

-160//1