Décomposition d'une matrice binaire

par **zixo** » 26 Avr 2006, 18:06

Bonjour,

Soit une matrice C binaire de taille NxM.
Est-il possible de trouver les matrices A et B (binaires, bien sûr), respectivement de taille Nx1 et 1xM, donnant C = BxA?
Si oui, par quel moyen ?

Merci d'avance pour s'être penché sur ce problème.

par **nuage** » 26 Avr 2006, 18:58

Salut,
je ne pense pas que ce soit possible : il y a 2^(MxN) matrices binaires de taille MxN et seulement 2^(M+N) produits du type proposé.
Sauf erreur de ma part.

par **zorg** » 26 Avr 2006, 20:23

Je trouve, Nuage, que ton argument est très pertinent.

par **nuage** » 26 Avr 2006, 22:12

Il reste toutefois à caractériser les matrices binaires MxN pour les quelles une telle décomposition est possible.

par **zorg** » 27 Avr 2006, 06:53

Dans l'énoncé c'est plutôt C=A x B

Voilà une idée sur la question pour avancer.
Dans une matrice du type A x B, il y a forcément des lignes ou des colonnes nulles (sauf si la matrice AxB est remplie que de 1).

Par exemple, on est sûr qu'une matrice du type

n'est pas de la forme A x B

par **Zebulon** » 27 Avr 2006, 07:57

zorg a écrit:Par exemple, on est sûr qu'une matrice du type

n'est pas de la forme A x B

Pourquoi pas? La matrice identité n'est pas interdite.

Décomposition d'une matrice binaire

Décomposition d'une matrice binaire

Qui est en ligne