Matrices inversibles à dénombrer

michel2
michel2
dans Combinatoire et Graphes
Bonjour. Je cherche à majorer le nombre de matrices carrées de taille n, inversibles, comportant sur chaque colonne deux 1 et (n-2) 0, par n! (n-1)^n. Vu le but, il suffirait de prouver qu'un tableau qui convient "contient" une matrice de permutation.. J'ai un peu de mal à bien utiliser la liberté des vecteurs colonnes. D'avance, merci pour vos réponses.

Réponses

  • P.
    P.
    $0\neq \det (a_{ij})=\sum_{\sigma\in S_n}\epsilon (\sigma)\prod_{i=1}^na_{i,\sigma(i)}$ entraine qu'il existe une permutation $\sigma$ telle que $$\prod_{i=1}^na_{i,\sigma(i)}\neq 0.$$ Est-ce-que cela ne te suffit pas?
  • YvesM
    YvesM
    Bonjour,

    $n \geq 2$ sinon il est difficile de placer deux $1.$

    Première colonne : $k=0$
    On a $n$ places pour le premier $1$ et $n-1$ places pour le second. Mais le résultat est le même que si les places sont inversées. Donc on a $n(n-1)/2-k$ colonnes différentes.

    Deuxième colonne : $k=1$
    Pareil mais la matrice doit être inversible et la deuxième colonne n’en peut pas égaler la première.
    Donc $n(n-1)/2-k$ colonnes différentes.

    Troisième colonne : $k=2$
    Pareil mais cette colonne doit différer des deux autres.
    Donc $n(n-1)/2-k$...

    Au total je trouve donc $\prod_{k=0}^{n-1} (n(n-1)/2-k)$ matrices différentes.

    Ajout : Il s’agit de matrices avec deux $1$ dans chaque colonne et dont les colonnes sont deux à deux distinctes. Mais ces matrices ne sont pas nécessairement inversibles.
    Une condition d’inversibilité est la non nullité du déterminant.
    Mais je ne sais pas écrire cette condition de façon utile au calcul...
  • jandri
    jandri
    Il ne suffit pas que les colonnes soient différentes deux à deux pour que la matrice soit inversible.

    Par exemple la matrice $\begin{pmatrix}1&0&0&1\\1&0&1&0\\0&1&1&0\\0&1&0&1\end{pmatrix}$ n'est pas inversible.
  • michel2
    michel2
    Bonjour et merci pour les réponses. Oui le fait qu 'on puisse extraire une matrice de permutation suffit car ensuite il ne reste plus qu' à placer le deuxième 1 dans chaque colonne . Bonne journée.
  • aléa
    aléa
    Est-ce que la question qu'on est en train de se poser, c'est si une matrice qui a exactement 2 "1" dans chaque colonnes, des zéro ailleurs est de rang $\ge n-1$ ?
  • jandri
    jandri
    Non si la matrice a deux lignes de 1 et les autres lignes sont nulles.
Connectez-vous ou Inscrivez-vous pour répondre.

Bonjour!

Pour participer au forum, cliquer sur l'un des boutons :

Connexion S'inscrire

Catégories

In this Discussion

Qui est en ligne 13

Lirone93i.zitoussim.c1zeste +9 Invités