The version 1.2 of CoxIter is realeased.
It can be found on GitHub: https://github.com/rgugliel/CoxIter
For the changelog, see here: https://github.com/rgugliel/CoxIter/blob/master/CHANGELOG.md
A GAP package is also in progress: https://github.com/rgugliel/CoxIterGAP
I have a symmetric matrix (containing numbers, or sequences of characters) which is eventually sparse (meaning that it contains a lot of zeros). I want to store this matrix in a computer program without loosing too much space. The idea is to create a vector from the matrix (hence we do not duplicate the information induced by the symmetry). Also, using an associative array we can drop all non-interesting entries if the matrix is sparse.
We start with an \(n\times n\) matrix with rows and columns labelled \( 0,\ldots, n-1 \) and we want to induce a bijection \( \iota: \{0,\ldots,n-1\}^2 \longrightarrow \left\{ 0,\ldots, \frac{n(n+1)}{2}-1 \right\} \). We will enumerate the elements of the first row \( 0,\ldots, n-1 \), the ones of the second row \( n,\ldots, 2n-2 \), etc.
If the pair \( (i,j) \) designates an element of the matrix, its index \( \iota(i,j) \) in the vector is given by
\[
\iota(i,j)=\frac{i(2n-1-i)}{2}+j
\]
Conversely, if \( k\in \left\{ 0,\ldots, \frac{n(n+1)}{2}-1 \right\} \) is the index of an element of the vector, then the corresponding entry of the matrix is on the row
\[
\textrm{row}(k)=\textrm{floor} \frac{(2n+1)-\sqrt{(2n+1)^2-8k}}{2},
\]
and column
\[
\textrm{col}(k)=k-\frac{\textrm{row}(k)\cdot\big(2n-1-\textrm{row}(k)\big)}{2}
\]
For a pair \( (i,j) \), we have to check that \( \textrm{row}\big( \iota(i,j) \big) = i \). Since the composition
\[
\textrm{row}\big( \iota(i,j) \big) = \textrm{floor}\frac{2n+1-\sqrt{(2n+1)^2-4i(2n-1-i)-8j}}{2}
\]
is increasing with respect to \( j \), we only have to check the equality in the extremal cases \( j = i \) and \( j = n-1 \). We find
\[
\textrm{row}\big( \iota(i,i) \big)=\textrm{floor} \frac{2n+1-\sqrt{ (2n-2i+1)^2}}{2} = i
\]
and
\[
\textrm{row}\big( \iota(i,n-1) \big)<\textrm{row}\big( \iota(i,n) \big)=\textrm{floor} \frac{2n+1-\sqrt{ (2n-2i-1)^2}}{2}=i+1,
\]
as required. It follows from these equalities that \( \textrm{col}\big( \iota(i,j) \big) = j \). The equality \( k = \iota\big( \textrm{row}(k), \textrm{col}(k) \big) \) is easy.
Publié dans Géométrie hyperbolique, Informatique et mathématiques
Laisser un commentaire
As I said in the previous post (more than a year ago, I know…), CoxIter is a computer program designed to compute invariants of hyperbolic Coxeter groups (probably that if you don’t know what it is you don’t need the program but, as usual, Wikipedia can provide interesting information).
The input of the program is a description of the Coxeter diagram of the group.
The output is the following:
Soon (during spring probably), the growth series and the growth rate will also be displayed.
CoxIter is a C++ program which can be built on Linux, Windows and OSX (I still have to add information about compilation on OSX). Information can be found here: http://coxiter.rgug.ch/doc/
An article describing the theory behind CoxIter was published in LMS Journal of Computation and Mathematics in December 2015. You can find this article here: https://dx.doi.org/10.1112/S1461157015000273
More information and download: https://coxiter.rgug.ch/
CoxIter est un programme développé en C++ qui permet de calculer certains invariants d’un groupe de Coxeter hyperbolique.
Ce programme, développé dans le cadre de ma thèse, permet de déterminer, pour un groupe de Coxeter hyperbolique:
Le programme sera publié sous licence libre bientôt. La page web officielle est celle ci: http://coxiter.rgug.ch/
Quand on poste au mauvais endroit…
http://rgug.ch/2014/03/06/kleinian-a-tool-for-visualizing-kleinian-groups-ubuntu/
Je ne peux résister à l’envie de partager cette petite blague:
A comathematician is a device for turning cotheorems into ffee.
Soit \(A\) une matrice de taille \(n\times n\) à coefficients réels. On désigne par \( A^\#\) la matrice complémentaire de \( A \).
La question que l’on se pose alors est la suivante: si \( B \) est une autre matrice de taille \( n\times n\) à coefficients réels, est-ce que l’on a \( (A\cdot B)^\# = B^\#\cdot A^\#\)?
J’ai vu un joli argument dans une discussion sur Wikipédia que je vous livre ici (sur la page réelle, on prend l’inverse de matrices pas forcément inversibles….)
Si les deux matrices sont inversibles, l’assertion découle directement de l’identité \( A\cdot A^\#=\det A\cdot I_n \).
On considère le polynôme réel \( p_A(t) = A + t\cdot I_n \). On constate que sauf pour au plus un nombre fini de valeurs de \(t \), les matrices \( p_A(t) \) sont inversibles (l’équation \(\det p_A(t)=0\) est une équation polynômiale de degré au plus \( n \) qui a donc au plus \( n \) solutions).
On considère maintenant la fonction continue \( f : \mathbb R\longrightarrow \textrm{Mat}(n\times n,\mathbb R) \) donnée par \[ f(t) =\big( p_A(t) \cdot p_B(t) \big)^\#-p_B(t)^\#\cdot p_A(t)^\# \]
S’il existe un \(t \) pour lequel \( f(t_0)\neq 0\), alors \(f \) ne s’annule pas dans un voisinage de \(t_0 \). Ce voisinage contient donc une infinité de matrices \( p_A(t) \) ou \( p_B(t) \) non inversibles, ce qui est en contradiction avec le point précédent. En particulier, \( f(0) = 0 \), comme on le voulait.
Deux vidéos montrant des collisions de boules dans l’espace hyperbolique de dimension 3:
A la suite du premier article sur les algèbres de Clifford, on va regarder quelques exemples. Dans tout cet article, on suppose que le corps de base \(K\) est les nombres réels. Un résultat classique (loi d’inertie de Sylvester) implique qu’une forme quadratique réelle sur un espace vectoriel de dimension \(n\) est isomorphe à une forme diagonale \(Q(x)=\sum_{i=1}^n a_i {x_i}^2\) avec \(a_i\in \{-1,0,1\}\). La paire \((p,q)\), où \(p\) (respectivement \(q\)) est le nombre de coéfficients \(a_i\) positifs (respectivement négatifs) est uniquement déterminée est est appelée la signature de la forme quadratique.
On va considérer pour la suite des formes de type \((0,n)\), c’est-à-dire \(Q(x)=-x_1^2-\ldots-x_n^2\) ainsi que la base canonique \(\{e_1,\ldots,e_n\}\) sur \(V\). Ainsi, la relation fondamentale pour cette algèbre de Clifford est: \(x^2=-|x|^2\).
En particulier, on a sur l’algèbre de Clifford \(Cl(V,Q)\) les relations suivantes:
Notation: On note l’algèbre de Clifford de dimension \(2^n\) construite sur \( V=\mathbb R^n\) via la forme quadratique \(-x_1^2-\ldots-x_n^2\) par \(Cl_n\).
Rien de très fou ici. On a une algèbre sur les réels de dimension 1. Ainsi, \(Cl_0=\mathbb R\).
On a ici une algèbre sur les réels de dimension 2 de base \(1,e_1\) avec la relation \(e_1\cdot e_1=-1\). On voit directement que cette algèbre est isomorphe à \(\mathbb C\).
On a ici une algèbre sur les réels de dimension 4 de base \(1,e_1,e_2,e_1\cdot e_2\) avec les relations \(e_1\cdot e_1=-1,e_2\cdot e_2=-1,e_2\cdot e_1=-e_1\cdot e_2\). On voit directement que cette algèbre est isomorphe à \(\mathbb H\), l’algèbre des quaternions de Hamilton.
On peut en fait montrer les isomorphismes suivants:
| \(n\) | algèbre de Clifford associée |
| 0 | \(\mathbb R\) |
| 1 | \(\mathbb C\) |
| 2 | \(\mathbb H\) |
| 3 | \(\mathbb H\times \mathbb H\) |
| 4 | \(\textrm{Mat}_2(\mathbb R)\) |
Henri Cartan a montré que les algèbres de Clifford « ont une période 8 », c’est-à-dire: pour tout entier \(n\), on a \(Cl_{n+8}=\textrm{Mat}_{16}(Cl_n)\)).
Le but de cet article est de présenter comment manipuler des quaternions avec le logiciel Maxima.
Pour commencer, il faut charger le package atensor qui va nous permettre de réaliser tous les calculs:
load(atensor);
Ensuite, on va effectuer les deux commandes suivantes:
init_atensor(clifford, 0, 0, 2); q(a,b,c,d):=a+b.v[1]+c.v[2]+d.v[1].v[2];
Maintenant, on peut commencer à travailler avec les quaternions. Les deux vecteurs de base sont stockés dans un vecteur v. Ainsi, i correspond à v[1] et j correspond à v[2]. Le vecteur k, quand a lui, correspond à v[1].v[2]. Par exemple, si je veux définir le nombre complexe \(z=1+2i\), je fais
z:1+2.v[1];
Si je veux le multiplier avec le quaternion \(3+4i+5j\), je fais:
(1+2*v[1]).(3+4*v[1]+5*v[2]);
et le résultat est
\(2\,\left( 5\,\left( {v}_{1} . {v}_{2}\right) +4\,\left( {v}_{1} . {v}_{1}\right) +3\,{v}_{1}\right) +5\,{v}_{2}+4\,{v}_{1}+3\)
Si on veut un résultat plus joli, on peut utiliser la commande atensimp:
atensimp((1+2*v[1]).(3+4*v[1]+5*v[2]));
qui nous renvoie
\(
2\,\left( 5\,\left( {v}_{1} . {v}_{2}\right) +3\,{v}_{1}-4\right) +5\,{v}_{2}+4\,{v}_{1}+3
\)
En combinant cela avec la fonction expand
expand(atensimp((1+2*v[1]).(3+4*v[1]+5*v[2]));)
on trouve finalement
\(
10\,\left( {v}_{1} . {v}_{2}\right) +5\,{v}_{2}+10\,{v}_{1}-5
\)
qui correspond au quaternion \(10k+5j+10i-5\).
On peut définir quelques commandes pour nous simplifier la vie:
conj(x):=subst([v[1]=-v[1],v[2]=-v[2],v[1] . v[2]=-v[1] . v[2]] , x); norm(x):=sqrt(expand(atensimp(x.conj(x)))); inverse(x):=conj(x).expand(atensimp(x.conj(x)))^(-1);
Ainsi, je peux calculer l’inverse du quaternion \(10k+5j+10i-5\):
inverse(q(-5,10,5,10))
On peut aussi faire des calculs plus généraux, comme par exemple multiplier les quaternions \(q(a,b,c,d)\) ainsi que \(q(e,f,g,h)\). Si vous essayez de le faire via la commande
expand(atensimp(q(a,b,c,d).q(e,f,g,h)));
, vous verrez que le résultat est plutôt… horrible (tellement horrible que je vous l’éparnge ;-))! Le problème est que nos variables a, b, …, h ne sont pas considérées comme réelles. On corrige le problème avec le code suivant:
declare([a,b,c,d,e,f,g,h],scalar); expand(atensimp(q(a,b,c,d).q(e,f,g,h)));
Comme indiqué dans l’introduction, on peut travailler avec une forme plus générale de l’algèbre des quaternions en considérant l’une des algèbres de Clifford. Dans ce cas, il faudrait modifier quelques petites choses: