Calcul matriciel avec Snap! et sa librairie APL

Un théorème d’algèbre linéaire en prime ;-)
mercredi 12 janvier 2022
par  Nathalie CARRIÉ

La puissance des blocs `map ` et ` combine ` de Snap! , associée à la nouvelle librairie APL (initialement `A programming language`, officieusement `Array Processing Language`) disponible depuis la version 6 de Snap! nous a permis d’explorer et de revisiter certains algorithmes de manipulation de matrices afin d’élaborer un outil de calcul matriciel dans Snap!.
C’est en testant les fonctions mises au point que nous avons mis en évidence un résultat original d’algèbre linéaire concernant les matrices carrées d’ordre n des entiers naturels de 1 à n².

Cet article se veut de présenter un nouvel outil de calcul matriciel [1] développé grâce à Snap!. Nous y aborderons des notions d’algèbre linéaire essentielles pour manipuler des matrices.
Tout d’abord, nous présenterons quelques `how to` :
- Comment générer la matrice Identité de taille n ?
- Comment générer une matrice de nombres aléatoires ?
- Sélection d’une ligne ou d’une colonne dans une matrice A
- Comment extraire le coefficient a_i,j d’une matrice A ?
- Comment calculer la trace d’une matrice à l’aide de la puissance du bloc `map`
- Comment calculer le déterminant d’une matrice donnée à l’aide d’une formule récursive ?
- Comment obtenir la comatrice d’une matrice donnée ?
- Comment obtenir l’inverse d’une matrice ?
- Puissances d’une matrice

Nous avons essayé dans l’écriture des blocs de cet outil de toujours avoir une pensée fonctionnelle et non pas une pensée séquentielle. On pourra se référer à cet article : `Tout est algorithme, tout est fonction`, dans lequel on explique qu’amener les algorithmes aux données est l’essence de la programmation fonctionnelle… [2]

La mise au point de cet outil nous a permis ensuite de découvrir de manière empirique un résultat original d’algèbre linéaire. Nous avons d’abord émis une conjecture sur les matrices carrées d’ordre n d’entiers naturels de 1 à n².
- Comment générer une telle matrice carrée ?
- Calcul du déterminant de cette matrice carrée pour n appartenant à 2, 3, 4, 5, 6, 7
- Conjecture : Dès que n ≥ 3, le déterminant de la matrice carrée d’ordre n dont les coefficients sont les entiers de 1 à n² (dans l’ordre naturel) est égal à zéro.
- Preuve très courte de ce théorème.

Depuis la version 6.0.0 de Snap!, une librairie très puissante pour les manipulations de vecteurs lui a été ajoutée par l’un de ses développeurs, Brian Harvey. C’est la librarie APL adaptée par Brian Harvey du langage APL : initialement /A Programming Language/, officieusement Array Processing Langage. Ce langage très puissant a été créé dans les années soixante pour décrire commodément des opérations globales sur des tableaux (de booléens, de données numériques et de caractères). Et l’intégration de cette librairie à Snap! lui confère de nouvelles vastes possibilités pour traiter les vecteurs de toute sorte.


 
 
 
Les formules utilisées dans cet article découlent d’un magnifique livre d’algèbre linéaire `Matrices et réduction ` de Cabane et Lebœuf édité chez Ellipses en 1990.


Déplier tous les blocs Replier tous les blocs

Découverte rapide de la librairie APL de Snap! 6 et ultérieur

Voici quelques exemples de fonctions qui nous seront utiles.

Quelques How To

Sélection d’une ligne ou d’une colonne dans une matrice donnée

Prenons par exemple la matrice carré d’ordre 4, B = [ [6,8,9,4],[9,6,1,7],[8,8,2,3],[1,5,7,8] ].

La matrice transposée de B est : tB = [ [6,9,8,1],[8,6,8,5],[9,1,2,7],[4,7,3,8] ]

On extrait la ième ligne :

On extrait la jème colonne :

On obtient alors respectivement la 3e ligne et la 2e colonne de la matrice B :

Comment extraire le coefficient a_i,j d’une matrice donnée ?

Voici la fonction qui renvoie ce coefficient a_i,j :

Ainsi, a_3,1 de B est 8.

Comment calculer la trace d’une matrice à l’aide de la puissance du bloc `map`

Comme tout un chacun sait (au moins vous qui lisez cet article...), la trace d’une matrice est la somme des éléments diagonaux.
Nous avons donc deux manière de calculer la trace : 1. version « old school » 2. avec le bloc ` map `

1. La version que j’appelle ` old school` se fait classiquement avec une boucle for :

2. Avec le bloc ` map`, c’est beaucoup plus élégant (et efficace ! ) :

Sur la matrice carré d’ordre 4, B = [ [6,8,9,4],[9,6,1,7],[8,8,2,3],[1,5,7,8] ],
que l’on peut importer en csv si on le souhaite ,
les coefficients diagonaux s’obtiennent en appliquant la fonction qui calcule les coefficients a_i,j de la matrice B à la matrice ρ(4) [3] grâce au bloc map.


Ainsi le bloc `map` permet d’appliquer la fonction a_i,j( )( )(B) aux éléments de la liste ρ(4)=[1,2,3,4] :

Il ne reste alors plus qu’à sommer les éléments diagonaux obtenus en appliquant l’opérateur + grâce au bloc `combine`.

Comment calculer le déterminant d’une matrice donnée à l’aide d’une formule récursive ?

On extrait d’abord la matrice Ɑ_i,j en enlevant les lignes i et j de la matrice de départ.

Étant donné une matrice carré d’ordre n, de terme général (a_i,j), son déterminant est donné par cette formule récursive :
 [4]
faisant intervenir la notion de cofacteur.

D’où le bloc récursif qui calcule le déterminant d’une matrice carré.

Comment obtenir la comatrice d’une matrice donnée ?

La comatrice d’une matrice donnée est la matrice de ses cofacteurs.

Le cofacteur d’indice i, k d’une matrice A est :

 [5]

D’où le bloc comatrice

La comatrice de la matrice B est donc :

Comment obtenir l’inverse d’une matrice ?

L’inverse d’une matrice est :

D’où le bloc qui calcule l’inverse d’une matrice donnée :

Comment obtenir la puissance d’une matrice ?

Nous proposons ce bloc récursif :

Exemple d’application :

Conjecture sur les matrices carrées d’ordre n d’entiers naturels de 1 à n²

Calcul du déterminant de cette matrice carrée pour n appartenant à 2, 3, 4, 5, 6, 7

Il suffit d’appliquer (mapper) la fonction det( ) à chacun des termes de la liste (2,3,4,5,6,7).

Il semblerait que l’on obtienne 0 dès que n ≥ 3.

Conjecture

La mise au point de notre outil de calcul matriciel nous a donc permis de découvrir ce résultat de manière empirique :
Dès que n ≥ 3, le déterminant de la matrice carrée d’ordre n dont les coefficients sont les entiers de 1 à n² (dans l’ordre naturel) est égal à zéro.

Preuve très courte de ce théorème.

Prenons u = (1,2,…,n) et a = (n,n, ...,n).
Les lignes de la matrice sont u, a + u, 2a + u, ..., (n-1)a + u.
Quand on développe le déterminant det(u, a + u, 2a + u, ..., (n-1)a + u), dans le cas où n ≥ 3, dans chaque terme, il y a au moins deux u ou au moins deux a, donc tous les termes sont nuls. [6]

A simple result in linear algebra found thanks to Snap ! and its APL Library

C’est le titre d’un `Lighting talk` du colloque Snap!Con 2021 au cours duquel j’ai présenté ce résultat.
Le keynote de cette contribution est disponible ici.

Snap! 7 permet la création de nouvelles catégories de blocs : la catégorie `Matrix tools`

Depuis la version 7 de Snap!, sortie pour Noël 2021, l’utilisateur peut créer ses propres catégories de blocs personnalisés.

Cela permet de ranger ses blocs dans des catégories particulières, ayant des couleurs choisies par l’utilisateur.

Vous trouverez le projet complet de calcul matriciel que je propose à cette adresse.
Bien sûr, il est incomplet mais je vous incite vivement à poursuivre ce travail pour le rendre encore plus utile...

L’utilisation de certains blocs de ce projet nécessite d’activer les extensions Javascript de Snap! comme ceci :
Sinon vous aurez ce genre de retour :

Je vous souhaite une agréable ballade dans ce projet de calcul matriciel. Afin de vous aider à découvrir ce projet et afin de vous en faciliter son utilisation, j’ai créé un lutin par étape :

N’hésitez pas à l’utiliser et à le faire utiliser par vos élèves de terminale et post-bac !

Vous trouverez au bas de cet article en téléchargement le support de la présentation de cet article qui s’est déroulée lors d’un séminaire de l’IREM de la Réunion à l’Université de Saint-Denis le 6 avril 2022
Et ci-dessous le document XML qui contient les catégories Snap! de Calcul Matriciel à importer dans une instance de Snap! :

Matrix project categories
Ce document contient les blocs utiles au calcul matriciel dans Snap!.
Livré sous licence CC BY-NC-SA 4.0

[1Cet outil se veut différent des autres outils que vous utilisez par sa simplicité d’utilisation amenée par la programmation visuelle (de simples blocs à déplacer) mais aussi surtout par la manière de manipuler les données des matrices.

[2`Functional programming is a different approach that is becoming important in “real world” programming because of parallelism, i.e., the fact that different processors can be manipulating the same data at the same time. `
Brian Harvey, Snap ! Reference Manual 7.0 page 48

[3La fonction ρ vient du langage APL

[4Cabane-Lebœuf page 100

[5Cabane-Lebœuf page 99

[6Un grand merci à Dominique Tournès pour la limpidité et la simplicité de cette preuve !


Documents joints

Calcul matriciel avec Snap ! et sa librairie (...)
Ce document est la présentation faite lors du séminaire de l’IREM du mercredi 6 avril 2022. Il met (...)

Commentaires