Champs finis: Calcul de l'inverse d'une matrice

Question

Je travaille avec des champs finis en Python. J'ai une matrice contenant des polynômes, chaque polynôme est représenté par un entier. Par exemple, le x^3 + x + 1 polynôme est représenté en 11, parce que:

x^3 + x + 1 ==> (1,0,1,1) ==> (8,0,2,1) ==> 8 + 0 + 2 + 1 ==> 11 

une matrice Étant donné, par exemple:

6, 2, 1 
7, 0, 4 
1, 7, 3 

Comment puis-je calculer l'inverse d'une matrice en Python? Je l'ai déjà mis en œuvre les fonctions suivantes (pour les polynômes, et non des matrices de polynômes): add(), sub(), mul(), div(), inv()

Answer 1

1. Supposons que votre corps fini est GF $ (8) $, toutes vos fonctions de calcul (tel que add(), mul()) doit calculer sur le même champ (GF (8)). La façon dont vous calculez une matrice inverse sur un corps fini est exactement la même que celle que vous calculez sur d'autres champs, et l'élimination de Gauss-Jordan peut juste le faire.

Ce qui suit est une partie de code (à partir de: https://github.com/foool/nclib/blob/master/gmatrixu8.cc) pour calculer la matrice inverse sur GF (256). J'espère que cela vous aidera.

void GMatrixU8::Inverse(){ 
    GMatrixU8 mat_inv; 
    int w = this->ww; 
    int dim; 
    int i, nzero_row, j; 
    int temp, jtimes; 

    dim = this->rr; 
    mat_inv.Make_identity(this->rr, this->cc, this->ww); 

    for(i = 0; i < dim; i++){ 
     nzero_row = i; 
     if(0 == Get(i,i)){ 
      do{ 
       ++nzero_row; 
       if(nzero_row >= dim){ ERROR("Non-full rank matrix!"); } 
       temp = Get(nzero_row, i); 
      }while((0 == temp)&&(nzero_row < dim)); 
      Swap_rows(i, nzero_row); 
      mat_inv.Swap_rows(i, nzero_row); 
     } 
     for(j = 0; j < dim; j++){ 
      if(0 == Get(j,i)) 
       continue; 
      if(j != i){ 
       jtimes = galois_single_divide(Get(j,i), Get(i,i), w); 
       Row_plus_irow(j, i, jtimes); 
       mat_inv.Row_plus_irow(j, i, jtimes); 
      }else{ 
       jtimes = galois_inverse(Get(i, i), w); 
       Row_to_irow(i , jtimes); 
       mat_inv.Row_to_irow(i , jtimes); 
      } 
     } 
    } 
    this->ele = mat_inv.ele; 
}