Matrices (I)
Matrices (I)
Définitions - Notations :
On appelle matrice à n lignes, p colonnes et à éléments (ou coefficients) dans K toute
application de t1, , nu t1, , pu dans K .
1
an,m
On appelle mème vecteur colonne de A le vecteur pa1,m , , an,m q, c’est un élément de Kn .
Définition :
Soient A, B P Mn,p pKq tels que A pai,j q1¤i¤n,1¤j ¤p et B pbi,j q1¤i¤n,1¤j ¤p
On dit que A et B sont égaux et on note A B si et seulement si : pi, j q P t1, , nu t1, , pu :
ai,j bi,j
b- Addition
Définition :
On appelle addition dans Mn,p pKq la loi interne, notée , définie par :
pai,j q1¤i¤n,1¤j¤p P Mn,p pKq et pbi,j q1¤i¤n,1¤j¤p P Mn,p pKq : pai,j q1¤i¤n,1¤j¤p pbi,j q1¤i¤n,1¤j¤p
pai,j bi,j q1¤i¤n,1¤j¤p
Remarque :
On ne somme que des matrices de même type.
Exemple
:
1 5 0 1
1 8 7
1
1
4 0
6 0 2
2 2
0
7
Proporiétés :
La loi est :
Associative et commutative.
Admet un élément neutre qui est la matrice de Mn,p pKq dont tous les termes sont nuls, on la note
On,p ou plus simplement O et on la nomme la matrice nulle.
Tout A paij q de Mn,p pKq admet un opposé noté A défini par : pi, j q P t1, , nu t1, , pu :
A paij q
Remarque :
L’élément neutre de Mn pKq On,n sera noté On .
Théorème :
pMn,p pKq, q est un groupe abélien
Définition :
On appelle multiplication par les scalaires la loi externe K Mn,p pKq ÝÑ Mn,p pKq, notée par . ou
par absence de symbole, définie par :
λ P K , paij qij P Mn,p pKq : λ.paij qij pλ.aij qij
Exemple
:
1 2 0 8
4
1 0 1
44 0
0
4
Propriétés :
Soient A, B P Mn,p pKq , soient λ, µ P K
1.A A
λ.pA B q λ.A λ.B
pλ µq.A λ.A µ.A
pλµq.A λ.pµ.Aq
Théorème :
pMn,p pKq, , .q est un K-espace vectoriel
Définition :
Pour pn, pq P pN q2 et pi, j q P t1, , nu t1, , pu , on note Eij la matrice de Mn,p pKq dont
le pi, j qème terme vaut 1 et tous les autres sont nuls. Les matrices Eij sont appelées les matrices
élémentaires de Mn,p pKq
Exemple :
0 0
0 1
Les matrices élémentaires de M1,3 pKq sont : E11 1 0 0 , E12 0 1 0 et E13 0 0 1
Propostion :
pEij qpi,jqPt1, ,nut1, ,pu est une base de Mn,p pKq, appelée base canonique de Mn,p pKq .
dim Mn,p pKq np, en particulier : dim Mn pKq n2
Exemple demanipulation
vectorielle
:
0 1
Soient A1 , A2 , A3 , A1
1 0 1 0 1 1
0 1 0 1 1 1 1 0
On se propose de montrer que la famille pAi q1¤i¤4 est une base de M2 pRq.
Il est clair que cardpAi q1¤i¤4 dim M2 pRq 4.
Il suffit donc de montrer que pAi q1¤i¤4 est libre .
Soient λ1 , λ2 , λ3 , λ4 P R tels que : λ1 A1 λ2 A2
λ3 A3 λ
4 A4 O2
λ3 λ4
Matriciellement :
λ1 λ2 λ3
λ3 λ4 λ1 λ2 λ3
00 00
En résolvant le système, on obtient : λ1 λ2 λ3 λ4 0
Ce qui permet de conclure.
d- Produit
Remarques :
Le produit AB n’est possible que si le nombre de colonnes de A est égal au nombre de lignes de B. Le
résultata alors autant de lignes que A et autant de colonnes que B.
En général AB BA, il se peut même que AB soit défini, mais pas BA.
Exemples :
4 8 0 5 1 12 4
4 0 4
4 0
12 4
1 3 3 2 2 11 5
0 1 0 1
2 1
1 2
2 1 0 1 1 2
n’est pas défini, par contre 1 2
1 2
2 1 5 1
0 1 0 5
Proposition :
Pseudo-distributivité à gauche :
A P Mn,p pKq , B, C P Mp,q pKq : ApB C q AB AC .
Pseudo-distributivité à droite :
A, B P Mn,p pKq, C P Mp,q pKq : pA B qC AC BC .
λ P K , A P Mn,p pKq , B P Mp,q pKq : pλAqB λpAB q ApλB q .
Pseudo-associativité :
A P Mn,p pKq, B P Mp,q pKq, C P Mq,r pKq : pAB qC ApBC q .
Proposition-Définition :
Le produit matriciel définit une loi de composition interne sur Mn pKq
pMn pKq, , ., q
est une K-algèbre
associative, unitaire.
1 O
On note In
..
.
Æ
P p q
Mn K l’élément neutre du produit matriciel.
O 1
Remarque :
La K-algèbre pMn pKq, , ., q n’est commutative que pour n 1, dans ce cas, elle est identifiable à
pK, , ., q.
Définition :
On dit que deux matrices A et B de Mn pKq commutent ssi : AB BA.
Remarque :
A P Mn pKq : A In In A A
Donc : In commute avec toute matrice de Mn pKq
Notation :
On notera diag pαi q1¤i¤n la matrice diagonale de Dn pKq dont la diagonale est la famille pαi q1¤i¤n
Exemples
:
6 0 0
0 i 0
diagp6, i, 101q P D3 pCq
0 0 101
In diagp1, 1, , 1q et On diagp0, 0, , 0q
Définition :
Soit la matrice carrée A paij q1¤i,j ¤n P Mn pKq.
A est dite triangulaire supérieure (ou : trigonale supérieure) si et seulement si :pi, j q P
t1, , nu2 : i ¡ j ùñ aij 0
On note Tn pKq l’ensemble des matrices triangulaires supérieures d’ordre n.
A est dite triangulaire inférieure (ou : trigonale inférieure) si et seulement si :pi, j q P
t1, , nu2 : i j ùñ aij 0
On note Tn pKq l’ensemble des matrices triangulaires inférieures d’ordre n.
Exemples
:
6 2 i 2
0 i 3
P T3 pCq
0 0 j
6 0 0
3 7 0
P T3 pRq
11 0 4
Proposition :
Dn pKq Tn pKq X Tn pKq
Théorème :
Dn pKq, Tn pKq et Tn pKq sont des sous-espaces vectoriels de Mn pKq
Dn pKq, Tn pKq et Tn pKq sont des sous-algèbres de la K-algèbre Mn pKq
Exemple :
0 1
An 1
An A 1
0
n
1
1 1
0 1
1 n 1
0 1
Résultat : n P N : An 1 n
0 1
Remarque :
Attention : pA B q2 A2 AB BA B2
Théorème :
Soit pA, B q P pMn pKqq2 tel que A et B commutent, on a alors m P N
pAB qm Am Bm̧m
m k m k
pA B qm k
A B (binôme de Newton)
k0
¸1
m
Am B m pA B q Ak B m1k
k 0
Remarque :
AB 0 n’implique pas que A 0 ou B 0
A
I2 possède
dans M2 pRq d’autres solutions que I2 et I2
2
Par conséquence,
1 0 1 0
0 1
Par exemple : ,
0 1
Définition :
On dit qu’une matrice A P Mn pKq est idempotente si A2 A.
On dit qu’une matrice A P Mn pKq est nilpotente s’il existe m P N tel que Am On .
Exemples :
A 22
1
1
est idempotente, en effet : A2
2 1
2 1
2 1
2 1
22
1
1
.
0 1 2
B 0 0 3
est nilpotente.
0 0 0
0 1 2 0 1 2 0 0 3 0 1 2 0 0 3 0 0 0
En effet : B 2 0 0 3
0 0 3
0 0 0
et B 3 0 0 3
0 0 0
0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Proposition :
Soit A P Dn pKq tel que A diag ppxi q1¤i¤n avec xi P K i P t1, , nu
On a alors : k P N : Ak diag ppxki q1¤i¤n
d- Matrices inversibles
Définition :
Une matrice A de Mn pKq est dite inversible si et seulement s’il existe A P 1
Mn pKq telle que
AA A A In
1 1
Exemple :
La matrice In est inversible et : In1 In
Proposition :
pGLn pKq, q est un groupe appelé groupe linéaire d’ordre n.
Lemme :
Soient A, B P Mn,p pKq.
Si : X P Mp,1 pKq : AX BX alors A B
Remarques :
x
Pour calculer l’inverse d’une matrice A P Mn pKq, on prend les deux matrices colonnes X y
P Mn,1 pKq
z
1
x
et Y y
P Mn,1 pKq, et on résout le système AX Y , où X est la matrice colonne inconnue (ie. On
1
1
z
cherche x, y et z en fonction de x , y et z )car :AX Y ùñ X A1 Y .
1 1 1
Il existe aussi la méthode de ”pivot de Gauss” pour calculer l’inverse d’une matrice, on exposera cette
méthode plus tard.
Exemple:
Soit A
1 2
1 3
Soit X x
y
et Y x
y
1 tels que : AX Y
1
# #
1
1 2 x
x
ðñ x
1
x 2y
ðñ x 3x 2y
1 1
ðñ x
31 12 x
ðñ
1 3 y y
1
y
1
x 3y y x y
1 1
y
1
y
X A1 Y
Proposition :
Soit pai q1¤i¤n une famille d’éléments dans K et soit la matrice A P Dn pKq telle que A diagpai q1¤i¤n .
Les propositions suivantes sont équivalentes :
(i) A est inversible
(ii) i P t1, , nu : ai r 0
De plus, dans ce cas : A1 diag p q1¤i¤n
1
ai
Soit la matrice A P Tn pKq (respectivement A P Tn pKq). On a équivalence entre :
(i) A est inversible
(ii) Les coefficients diagonaux de A sont tous non nuls.
De plus, si tel est le cas, A1 P Tn pKq (respectivement A1 P Tn pKq)
4- Transposition
a- Définition et propriétés :
Définition :
a11 a1p
Pour toute matrice A paij q1¤i¤n,1¤j ¤p .. .. Æ de M pKq, on appelle transposée de
.
.
n,p
an1 anp
Mp,n pKq définie par :
A la matrice notée t̂A de
a11 an1
t̂A paij q1¤j ¤p,1¤i¤n .. .. Æ (Ainsi le coefficient d’indice pj, iq de t̂A est égal au coeffi-
.
.
a1p anp
cient d’indice pi, j q de A)
Remarque :
Les colonnes et lignes de t̂A correspondent respectivement aux lignes et colonnes de A.
Exemple :
0 0
A , donc : t̂A 1 0
0 1 2
0 0 3
2 3
Proposition :
T : Mn,p pKq ÝÑ Mp,n pKq
M ÞÝÑt M
L’application est un isomorphisme de K-espaces vectoriels.
Définitions :
i)
Une matrice A de Mn pKq est dite symétrique si et seulement si : t̂A A
On note Sn pKq l’ensemble des matrices symétriques d’ordre n à coefficients dans K
ii)
Une matrice A de Mn pKq est dite antisymétrique si et seulement si : t̂A A
On note An pKq l’ensemble des matrices antisymétriques d’ordre n à coefficients dans K
Proposition :
Sn pKq est un sous-espace vectoriel de Mn pKq de dimension npn2 1q
An pKq est un sous-espace vectoriel de Mn pKq de dimension npn2 1q
Proposition :
pA, B q P pSn pKqq2 : AB P Sn pKq ðñ AB BA (ie. A et B commutent)
A P Sn pKq X GLn pKq : A1 P Sn pKq
Théorème :
Les sous-espaces vectoriels Sn pKq et An pKq sont supplémentaires dans Mn pKq
Définitions :
.
Soient A, B P Mn,p pKq, A et B sont dites équivalentes et on note AeqB si et seulement s’il existe
deux matrices inversibles P P Mn pKq et Q P Mp pKq telles que : A P BQ.
Soient A, B P Mn pKq, A et B sont dites semblables et on note A B si et seulement s’il existe
P P Mn pKq inversible telle que : A P BP 1
Proposition :
Les relations eq et sont des relations d’équivalence respectivement dans Mn,p pKq et Mn pKq
Remarques :
Puisque les composantes d’un vecteur dépendent de la base choisie, il est nécessaire de préciser celle-ci.
Toutes les matrices des composantes d’un vecteur appartiennent à Mn,1 pKq .
Exemples :
Soit dans R3 rX s , le polynôme P 2X 3
8X 3, la matrice-colonne des composantes de P dans la base
3
8Æ
canonique B p1, X, X 2 , X 3 q est : M atB pP q 0
Æ
2
Théorème :
MB : E ÝÑ Mn,1 pKq
x ÞÝÑ M atB pxq
En conservant les notations de la définition ; L’application est un isomorphisme
de K-espace vectoriel.
Définition :
Soient E un K-ev , n dim pE q , B pe1 , , en q une base de E, p P N , F pV1 , , Vp q une famille
finie de p éléments de E, et, pour chaque j de t1, , pu, pa1j , , anj q les composantes de Vj dans
ņ
B : j P t1, , pu , Vj akj ek
k 1
a11 a1p
La matrice paij q1¤i¤n,1¤j ¤p .. Æ de M pKq s’appelle la matrice de la famille F
.
.. .
n,p
an1 anp
relativement à la base B et est notée M atB pF q ou M atB pV1 , , Vp q
Remarque :
Dans le cas p 1, on retrouve la notion de matrice des composantes d’un vecteur.
Exemples :
Considérons l’espace vectoriel R3 muni de sa base canonique B pp1, 0, 0q, p0, 1, 0q, p0, 0, 1qq
Soient x1 p1, 2, 3q, x2 p2, 0, 1q, x3 p1, 0, 1q et x4 p1, 1, 1q quatre vecteurs de R3
Définition :
$
'
&E, F deuxK ev, p dim pE q, n dim pF q
Soient B pe1 , , ep qune base de E, C pf1 , , fn qune base de F .
'
f P LpE, F q
%
ņ
Pour chaque j de t1, , pu , notons pa1j , , anj q les composantes de f pej q dans C : f pej q akj fk
k 1
Remarque :
Lorsque A M atB,C pf q, on dit que f est représentée par A dans les bases B et C, ou que A représente
f dans B et C
La matrice représentative de f dépend du choix des bases B et C, il est donc nécessaire de préciser celles-ci.
Théorème :
Soient E et F deux K-espaces vectoriels munis respectivement des bases B et C
MB,C : LpE, F q ÝÑ Mn,p pKq
u ÞÝÑ M atB,C puq
L’application est un isomorphisme de K-espaces vectoriels.
Exemples :
Soit f : R3 ÝÑ R2 l’application linéaire définie par : f px, y, zq px 2y z, x yq
Formons la matrice de f relativement aux bases canoniques B pe1 , e2 , e3 q et B pu1 , u2 q respectivement
1
de R3 et R2
On a :
f pe1 q f p1, 0, 0q p1, 1q u1 u2
f pe2 q f p0, 1, 0q p2, 1q 2u1 u2
f pe3 q f p0, 0, 1q p1, 0q u1
On en déduit :
1 2 1
M atB,B pf q P M2,3 pRq
1 1 0
1
Théorème :
Soient E et F deux K-espaces vectoriels munis respectivement des bases B et C, u P LpE, F q
La matrice de u dans les bases B et C est l’unique matrice A P Mn,p pKq vérifiant :
x P E y P F : y upxq ðñ Y AX avec X M atB pxq et Y M atC pyq
Définitions :
Soit A P Mn,p pKq
On appelle noyau de A le sev de Mp,1 pKq noté KerpAq, défini par : KerpAq tX P Mp,1 pKq, AX
0u
On appelle image de A le sev de Mn,1 pKq noté ImpAq, défini par : ImpAq tY P Mn,1 pKq, DX P
Mp,1 pKq, Y AX u tAX, X P Mp,1 pKqu
Cela veut dire que les éléments de KerpAq sont les représentations matricielles des éléments de Kerpuq et
que les éléments de ImpAq sont les représentations matricielles de Impuq (relativement aux bases B et C)
Exemple :
Soit E un R-ev muni d’une base B pe1 , e2 , e3 q
1 1 2
Soit u un endomorphisme de LpE q dont la matrice dans B est : A M atB puq 1 1 0
1 0 1
Soit x x1 e1 x2 e2 x3 e3 PE
x1 x2 2x3
On a : M atB pupxqq AX x1 x2
x1 x3
On peut étudier$Kerpuq en étudiant KerpAq, c’est-à-dire en résolvant l’équation matricielle AX 03,1
&x1 x2 2x3 0
' #
AX 03,1 ðñ x1 x2 0
'
ðñ xx1
x2
x3
x1 x3 0
% 1
1
KerpAq tα 1
{α P Ru
1
Ainsi, Kerpuq tαpe1 e2 e3 q{α P Ru
Donc : Kerpuq V ectpe1 e2 e3 q
Proposition :
$
'
&E, F, GtroisK ev
Soient B, C, Ddes bases deE, F, Grespectivement
'
f P LpE, F q, g P LpF, Gq
%
On a : M atB,D pgof q pM atC,D pg qqpM atB,C pf qq
Proposition :
Soient E un K-ev de dimension n muni d’une certaine base B, f P LpE q, A la représentation matricielle
de f dans la base B, on a :
f est nilpotant ðñ A est nilpotante
f est un projecteur ðñ A2 A
f est une symétrie ðñ A2 In
c- Bijection et inversibilité
Théorème :
Soient E et F deux K-espaces vectoriels de même dimension munis respectivement des bases B et C,
f P LpE, F q, A M atB,C pf q. Les propositions suiventes sont équivalantes :
i- f est un isomorphisme.
ii- A est inversible.
De plus, dans ce cas : M atC,B pf 1 q A1
Corollaire :
Soient E un K-espace vectoriel de dimension n muni d’une base B, f P LpE q. les propositions suivantes
sont équivalantes :
i- f est un automorphisme
ii- M atB pf q P GLn pKq
De plus, si tel est le cas : M atB pf 1 q rM atB pf qs1
Exemple :
Soit E un R-espace vectoriel muni de la base B pe1 , e2 , e3 q et soit F un R-espace vectoriel muni de la base
C p u 1 , u 2 , u 3 q.
Soit f : E Ñ F l’application linéaire définie par sa représentation matricielle :
1 0 1
M atB,C pf q 0 0 2
1 1 1
Montrons que f est un isomorphisme,
pour cela, on montre que M atB,C pf q est inversible.
x1 y1
Soient X x2
et Y y2
de M3,1 pRq telles que : AX Y
x3 y3 $
$
&x3 2
1 0 1 x1 y1 '
& x 1 x 3 y 1
'
'
y2
Définition :
Soit E un K-espace vectoriel de dimension n muni de deux bases B pe1 , , en q et B pe1 , , en q.
1 1 1
On appelle matrice de passage de la base B à la base B la matrice de Mn pKq notée PBB ou plus
1
1
Exemple :
Soit E R3 rX s muni de sa base canonique B p1, X, X 2 , X 3 q
La famille C p1, 1 X, p1 X q2 , p1 X q3 q est une base de E (démonstration simple et laissée en exercice)
Ecrivons la matrice de passage PB,C :
On sait que :1 1 0X 0X 2 0X 3
1 X 1 1X 0X 2 0X 3
Proposition :
Soit E un K-espace vectoriel.
Pour toutes bases B, B de E : PBB
1
1 M atB B pIdE q
1
Proposition :
1 2
Soit E un K-espace vectoriel de dimension n, B, B , B des bases de E. On a :
PBB PBB PB B
2 1 1 2
PBB In
PBB est inversible et rPBB s1 PB B
1 1 1
On a : X P X et X P X
1 1
On a : A Q1 AP
1
P M atB pB q.
1
On a : A P 1 AP
1
Exemple :
E un R ev muni
Soit d’une base B pe1 , e2 , e3 q et soit f P L pE q définie par : M atB pf q A avec
2 1 1
A 3 2 1
.
3 5 4
$
e2 e3 '
&u1
Soit C pu1 , u2 , u3 q une famille d’éléments dans E définie par : u2 e1 e2 e3 .
'
u3 e1 e2 2e3
%
Il est simple de vérifier que C est libre (laissé en exercice), donc
C est une autre
base de E.
0 1 1
La matrice de passage P de B à C est donc : P M atB pC q 1 1 1
.
1 1 2
On obtient enfin
:
0 1 1 p1qn 0 0 1 1 0 0 0 0 1 1 1
n P N : An 1 1 1
0 2n 0
1 1 1
p1qn 1 1 0
2n 1 1 1
1 1 2 0 0 3n 0 1 1 1 1 0 1 1 1
0 1 1
3n 0 1 1
0 2 2
3- La trace
a- Trace d’une matrice carrée
Définition :
ņ
On appelle trace d’une matrice carrée A paij q P Mn pKq le scalaire : trpAq aii
i 1
Exemples :
n P N :trpIn q n
2 1 1
Soit A 1 3 1
, trpAq 3
1 0 2
Proposition :
Pour toutes matrices carrées A et B de même ordre et pour tous scalaires a, b P K :
trpaA bB q atrpAq btrpB q
trpt Aq trpAq
Autrement dit, l’application tr : Mn pKq ÝÑ K est une forme linéaire invariante par transposition.
Théorème :
A P Mn,p pKq , Mp,n pKq : trpAB q trpBAq
Proposition :
pA, B q P pMn pKqq2 : A B ùñ trpAq trpB q
b- Trace d’un endomorphisme
1
En effet, Soient B et B deux bases de E.
Notons, P M atB pB q , A M atB pf q et A M atB pf q
1 1
1
On sait que : A P A P 1
1
Théorème :
La trace définit une forme linéaire sur LpE q, vérifiant : pf, gq P pLpE qq2 : trpf ogq trpgof q
Définition :
Soit A P Mn,p pKq. On appelle rang de A, et on note rg pAq le rang de la famille des colonnes de A
dans Mn,1 pKq
Théorème :
Si F px1 , , xp q une famille de vecteurs d’un K-ev E et si A est la matrice de F dans une certaine
base B de E alors : rgF rg pAq
Théorème :
Si u est une application linéaire d’un K-ev E vers un K-ev F et si A est la matrice de u relative à des
bases B et C respectivement de E et F alors : rg pAq rg puq.
Proposition :
A P Mn,p pKq : rgpAq ¤ M inpn, pq
A P Mn pKq : rg#pAq n ðñ A P GLn pKq
A P Mn,p pKq : PQ PP GL p pKq, rg pAP q rg pAq
GL pKq, rg pQAq rg pAq
n
Proposition :
Soient AP Mn,p pKq , r rg
pAq. Alors A est équivalente à la matrice Jn,p,r définie par :
Or,pr
Jn,p,r
Ir
Onr,r Onr,pr
Remarque :
Jn,p,0 0
Proposition :
pA, B q P pMn,p pKqq2 : AeqB ðñ rgpAq rgpB q
Proposition :
Soit A P Mn,p pKq.
Les opérations élémentaires sur les colonnes et sur les lignes de A conservent le rang de A
Exemples
:
1 2 1
A 1 3 2
1 1 0
1 2 1 1 2 1 1 2 1
rg pAq rg 1 3 2
rg 0 0 1
rg 0 0 1
2
1 1 0 0 1 1 0 0 0
Opérations effectuées :
Opération 1 : L2 ÝÑ L2 L1 et L3 ÝÑ L3 L1
Opération 2 : L3 ÝÑ L3 L2
1 1 1
1 1 1Æ
B 2 1 1
Æ
1 2 1
1 1 1 1 0 0
1 1 1Æ 1 0Æ
rg pB q rg Æ rg
1
3
2 Æ
2 1 1
2 1
1 2 1 1 1 2
Opération effectuée :
C2 ÝÑ C2 C1 et C3 ÝÑ C3 C1
Remarque :
Les opérations élémentaires doivent être effectuées successivement et non simultanément.
Contre-exemple
:
I2 ÝÑ L1 ÝÑ L2
1 0
devient, en effectuant L1 L2 et L2 L1 :
0 1
Simultanément : 1 1 (Faux)
1 1
Successivement : 1 1
2 1
[puce ]Des opérations élémentaires uniquement sur les lignes ( ou uniquement les colonnes) de A qui
transforme A en In .
Ces mêmes opérations à In , la matrice obtenue est A1 .
Exemple
:
1 1 1
A 1 1 0
2 1 1
1 1 1 1 0 0
1 1 0 0 1 0
2 1 1 0 0 1
1 1 1 1 0 0
0 0 1 1 1 0
0 1 3 2 0 1
1 1 1 1 0 0
0 1 3 2 0 1
0 0 1 1 1 0
1 1 1 1 0 0
0 1 3 2 0 1
0 0 1 1 1 0
1 1 0 0 1 0
0 1 0 1 3 1
0 0 1 1 1 0
1 0 0 1 2 1
0 1 0 1 3 1
0 0 1 1 1 0