Generation d'une matrice inversible a coefficients binaires

Version imprimable

21/04/2011, 14h14
zenaf

Generation d'une matrice inversible a coefficients binaires

Bonjour,
Voila je suis confronté a un probleme. Je cherche a générer des matrices inversibles 32x32 (et accessoirement plus) à coefficient dans Z/2Z.

Pour l'instant j'utilise un algorithme qui genere une matrice de nxn aléatoirement et qui grace a l'algorithme de Gauss-Jordan me détermine l'inversibilité de celle ci. Si tel n'est pas le cas, je recommence avec une nouvelle matrice fraichement générée.

Si cette technique fonctionne bien pour des petits n (j'entend n < 16), l'algorithme est interminable au dela.

Existe t'il un algorithme performant pour réaliser cette opération?

Merci de vos réponses.
21/04/2011, 15h39
Thierry Chappuis

L'algogithme de Gauss-Jordan te permet d'inverser la matrice. Pour décider si une matrice est inversible, il suffit en principe d'en calculer le déterminant.

Avec mes meilleures salutations

Thierry

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/*
	Return 1 if the rank is full, 0 else
*/
 
int gauss_jordan(int** M,int m,int n){
  int i1,i2,j;
  int* tmprow=NULL;
  int maxrow;
  int** matrix;
 
//Copy M in temporary matrix
  matrix=(int**)malloc(m*sizeof(int*));
  for(i1=0;i1<m;i1++){
		matrix[i1]=(int*)malloc(n*sizeof(int));
  }
 
  for(i1=0;i1<m;i1++){
	for(j=0;j<n;j++){
		matrix[i1][j]=M[i1][j];
  }
	}
 
  for (i1=0;i1<m;i1++){
	maxrow=i1;
	for (i2=i1+1;i2<m;i2++){
      if (matrix[i2][i1] > matrix[maxrow][i1]);
        maxrow = i2;
	}
 
	if(maxrow!=i1){
		//swapping two lines
	    tmprow=matrix[i1];
	    matrix[i1]=matrix[maxrow];
    	matrix[maxrow]=tmprow;
	}
 
	//Matrice singuliere
   	 if (matrix[i1][i1]==0){
		for(i2=0;i2<m;i2++){
			free(matrix[i2]);
		}
		free(matrix);
 
			return 0;
	}
 
 
	//replaces all lines if i1 coefficient is not 0
	for (i2=0;i2<m;i2++){
		if(i1 != i2 && matrix[i2][i1]==1) 
			for (j=i1;j<n;j++)
		   	    matrix[i2][j] ^= matrix[i1][j];
	}
 
  }
 
	for(i1=0;i1<m;i1++){
		free(matrix[i1]);
	}
	free(matrix);
	return 1;
}

J'ai modifié l'algorithme de Gauss Jordan pour qu'il renvoie un booleen en cas d'inversibilité et plus generalement pour savoir si la matrice est de rang plein.
De plus j'ai essayé avec le déterminant calculé de facon reccursive. Cependant mon algorithme reste sans nul doute plus efficace. Non le probleme se situerais je pense plutot dans la facon de générer les lignes, peut être en prenant en compte les lignes précédentes ?

31/03/2017, 16h11
xialihn

Je me permets de reprendre cette ancienne discussion, car j'ai exactement le meme problème.

Zenaf, pour l'instant, soit j'utilise la meme méthode que toi, soit un algo similaire qui nécessite exactement 2^n operations pour générer une de ces matrices (ce qui me limite aussi à n~30).

Je pense partir de la matrice identité n x n, puis appliquer aléatoirement des operations sur les lignes (sum modulo 2 de 2 lignes ou permutations).
Chacune des matrices obtenues sera encore de rang n. Mais rien ne me garanti d'échantillonner "uniformément"....

As-tu trouvé une solution plus efficace?