Transformée de matrice carrée ?

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: ijk

Bonjour

J'ai toujours été fasciné par la découverte de la tranformation de Fourier avec tout ce qu'elle apporte en traitement des signaux et la multiplication des grands nombres. Sans parler de la transformation rapide et discret de Fourier qui permet de passer d'une complexité en O(n) à O(log(n))

Voilà depuis quelque temps je me demande pourquoi n'existerait-il pas aussi une transformée permettant de voir la multiplication de matrices carrées d'une autre manière !? Pour éviter toute confusion, je parle bien ici des matrices utilisées couramment en mathématiques et pas d'une de matrices de pixels/points pour en faire un convolution ou autre.

Pour commencer plus simplement j'aimerai déjà réaliser la multiplication d'une matrice carrée par elle même

Comme chacun sait : le produit matriciel ordinaire d'une matrice carrée A vaut Ai,j = somme de (Ai,k*Ak,j) pour k=[1..largeur de A]

A l'instar de la Transformée de Fourier j'aimerai que ma transformée permet de passer au produit composante par composante : Ai,j = Ai,j * A.i,j

Avec
'x' le produit matriciel ordinaire
'*' le produit matriciel composante par composante
'T()' la fonction transformant une matrice
'iT()' la fonction inverse

A x A = iT(T(A)*T(A))

Quel intérêt à cela ?

Et bien... ceci permettrait surement de calculer A puissance n avec une complexité algorithmique constante. Et puis en rêvant bien... p'être qu'il existera aussi un simplification comme la tranformée rapide de Fourier. Le summum ! Du jamais vu réduite la complexité du produit matriciel ordinaire à O(n²log(n)) !!!!!


Alors comment trouver un telle transformation ou... comment prouver quel n'existe pas !?

On pour commencer par le cas le plus simple une matrice 2X2 ?

avec la propriété

Code:
[A B]-1 = [ D -B]
[C D]     [-C  A]/(AD - BC)

Voila si certains ont certaines réponses car j'ai la 'chance' d'avoir des connaissances mathématique assez limités pour m'imaginer que l'on peut TOUT réaliser avec

Note : Je ne cherche pas surtout pas algo genre V. Strassen. Je vois plutôt l'utilisation de nombres Complexes


Posted by: ijk

Ah j'ai oublié de noter que le produit matriciel normal n'est pas commutatif

C'est pourquoi je cherche avant tout un transformation qui réalise

A² = iT(T(A)²)

où '²' est le produit normal d'une matrice par lui même.
et '²' est la mise au carré individuelle de chaque composant.

Et de façon général :
A^n = iT(T(A)^n)


Posted by: Dominique Lefebvre

Citation:
Posté par ijk
Ah j'ai oublié de noter que le produit matriciel normal n'est pas commutatif


Vraiment !!! Quelle surprise


Posted by: ijk

Citation:
Posté par Dominique Lefebvre
Vraiment !!! Quelle surprise

Mon 'oublier' ne signifie pas que je viens de 'decouvrir' les règles du produit matriciel Seulement que je n'ai peut être pas à en tenir compte avec seulement le calcul de A^n

Pourtant je tenais à le préciser avant que l'on me sorte qu'une 'transformée unique' ne peut exister à cause de la non commutativité du produit.

Autrement j'aimerai bien avoir des reponses autres que "Retourne dans ta cours, tu ne sais pas de quoi tu parles !" Si possible bien sûr Problème trop trivial !?

Je suis au courant que beaucoup² d'études on été faite sur les matrices. Seulement je n'ai rien vu se rapprochant d'une pseudo-transformée de Fourier. Est ce une impasse ?

A titre de comparaison la transformée de Fourier peut être directement applicable sur une 'matrice cyclique' pour calculer tout A^n










-