2024-07-07

667: For Rectangle Matrix over Principal Integral Domain, There Are Some Types of Rows or Columns Operations Each of Which Can Be Expressed as Multiplication by Invertible Matrix from Left or Right

<The previous article in this series | The table of contents of this series | The next article in this series>
description/proof of that for rectangle matrix over principal integral domain, there are some types of rows or columns operations each of which can be expressed as multiplication by invertible matrix from left or right

Topics


About: ring

The table of contents of this article

Starting Context

Target Context


  • The reader will have a description and a proof of the proposition that for any rectangle matrix over any principal integral domain, there are some types of rows or columns operations each of which can be expressed as the multiplication by an invertible matrix from left or right.

Orientation


There is a list of definitions discussed so far in this site.

There is a list of propositions discussed so far in this site.

Main Body

1: Structured Description


Here is the rules of Structured Description.

Entities:
R: ∈{ the principal integral domains }
U: ∈{ the units of R}
M: ∈{ the m x n matrices over R}
u: ∈U
t: ∈R
{r,s}: ⊆{1,...,m}
v: ∈{1,...,n}
d: ∈gcd(Mvr,Mvs)
{w,x}: ⊆R, wMvr+xMvs=d
I: = the m x m identity matrix 
A(r,u): =I with (r,r)1 replaced by u
B(r,s): =I with (r,r)1 replaced by 0,(r,s)0 replaced by 1,(s,r)0 replaced by 1, and (s,s)1 replaced by 0
C(r,s,t): =I with (s,r)0 replaced by t
D(r,s,v,d,w,x): =I with (r,r)1 replaced by w,(r,s)0 replaced by x,(s,r)0 replaced by −Mvs/d, and (s,s)1 replaced by Mvr/d
{r′,s′}: ⊆{1,...,n}
v′: ∈{1,...,m}
d′: ∈gcd(Mr′v′,Ms′v′)
{w′,x′}: ⊆R, w′Mr′v′+x′Ms′v′=d′
I′: = the n x n identity matrix 
A′(r′,u): =I′ with (r′,r′)1 replaced by u
B′(r′,s′): =I′ with (r′,r′)1 replaced by 0,(s′,r′)0 replaced by 1,(r′,s′)0 replaced by 1, and (s′,s′)1 replaced by 0
C′(r′,s′,t): =I′ with (r′,s′)0 replaced by t
D′(r′,s′,v′,d′,w′,x′): =I′ with (r′,r′)1 replaced by w′,(s′,r′)0 replaced by x′,(r′,s′)0 replaced by −Ms′v′/d′, and (s′,s′)1 replaced by Mr′v′/d′
//

Statements:
A(r,u)M multiplies the r-th row by u
∧
B(r,s)M swaps the r-th row and the s-th row
∧
C(r,s,t)M adds the r-th row multiplied by t to the s-th row
∧
D(r,s,v,d,w,x)M replaces the r-th row by the r-th row multiplied by w plus the s-th row multiplied by x and replaces the s-th row by the r-th row multiplied by −Mvs/d plus the s-th row multiplied by Mvr/d, resulting with (D(r,s,v,d,w,x)M)vr=d and (D(r,s,v,d,w,x)M)vs=0
∧
∃A(r,u)−1(A(r,u)−1A(r,u)=A(r,u)A(r,u)−1=I)
∧
∃B(r,s)−1(B(r,s)−1B(r,s)=B(r,s)B(r,s)−1=I)
∧
∃C(r,s,t)−1(C(r,s,t)−1C(r,s,t)=C(r,s,t)C(r,s,t)−1=I)
∧
∃D(r,s,v,d,w,x)−1(D(r,s,v,d,w,x)−1D(r,s,v,d,w,x)=D(r,s,v,d,w,x)D(r,s,v,d,w,x)−1=I)
∧
MA′(r′,u) multiplies the r′-th column by u
∧
MB′(r′,s′) swaps the r′-th column and the s′-th column
∧
MC′(r′,s′,t) adds the r′-th column multiplied by t to the s′-th column
∧
MD′(r′,s′,v′,d′,w′,x′) replaces the r′-th column by the r′-th column multiplied by w′ plus the s′-th column multiplied by x′ and replaces the s′-th column by the r′-th column multiplied by −Ms′v′/d′ plus the s′-th column multiplied by Mr′v′/d′, resulting with (MD′(r′,s′,v′,d′,w′,x′))r′v′=d′ and (MD′(r′,s′,v′,d′,w′,x′))s′v′=0
∧
∃A′(r′,u)−1(A′(r′,u)−1A′(r′,u)=A′(r′,u)A′(r′,u)−1=I′)
∧
∃B′(r′,s′)−1(B′(r′,s′)−1B′(r′,s′)=B′(r′,s′)B′(r′,s′)−1=I′)
∧
∃C′(r′,s′,t)−1(C′(r′,s′,t)−1C′(r′,s′,t)=C′(r′,s′,t)C′(r′,s′,t)−1=I′)
∧
∃D′(r′,s′,v′,d′,w′,x′)−1(D′(r′,s′,v′,d′,w′,x′)−1D′(r′,s′,v′,d′,w′,x′)=D′(r′,s′,v′,d′,w′,x′)D′(r′,s′,v′,d′,w′,x′)−1=I′)
//

d, {w,x}, d′, and {w′,x′} exist, by the proposition that any principal integral domain is a greatest common divisors domain, and for each 2 elements on the principal integral domain, each of the greatest common divisors of the 2 elements is a one by which the sum of the principal ideals by the 2 elements is the principal ideal.

2: Natural Language Description


For any principal integral domain, R, the set of the units, U, any mxn matrix over R, M, any u∈U, any t∈R, any {r,s}⊆{1,...,m}, any v∈{1,...,n}, any d∈gcd(Mvr,Mvs), any {w,x}⊆R such that wMvr+xMvs=d, the mxm identity matrix, I, I with (r,r)1 replaced by u, A(r,u), I with (r,r)1 replaced by 0,(r,s)0 replaced by 1,(s,r)0 replaced by 1,(s,s)1 replaced by 0, B(r,s), I with (s,r)0 replaced by t, C(r,s,t), and I with (r,r)1 replaced by w,(r,s)0 replaced by x,(s,r)0 replaced by −Mvs/d, and (s,s)1 replaced by Mvr/d, D(r,s,v,d,w,x), A(r,u)M multiplies the r-th row by u, B(r,s)M swaps the r-th row and the s-th row, C(r,s,t)M adds the r-th row multiplied by t to the s-th row, D(r,s,v,d,w,x)M replaces the r-th row by the r-th row multiplied by w plus the s-th row multiplied by x and replaces the s-th row by the r-th row multiplied by −Mvs/d plus the s-th row multiplied by Mvr/d, resulting with (D(r,s,v,d,w,x)M)vr=d and (D(r,s,v,d,w,x)M)vs=0, ∃A(r,u)−1(A(r,u)−1A(r,u)=A(r,u)A(r,u)−1=I), ∃B(r,s)−1(B(r,s)−1B(r,s)=B(r,s)B(r,s)−1=I), ∃C(r,s,t)−1(C(r,s,t)−1C(r,s,t)=C(r,s,t)C(r,s,t)−1=I), and ∃D(r,s,v,d,w,x)−1(D(r,s,v,d,w,x)−1D(r,s,v,d,w,x)=D(r,s,v,d,w,x)D(r,s,v,d,w,x)−1=I).

For any {r′,s′}⊆{1,...,n}, any v′∈{1,...,m}, any d′∈gcd(Mr′v′,Ms′v′), any {w′,x′}⊆R such that w′Mr′v′+x′Ms′v′=d′, the nxn identity matrix, I′, I′ with (r′,r′)1 replaced by u, A′(r′,u), I′ with (r′,r′)1 replaced by 0,(s′,r′)0 replaced by 1,(r′,s′)0 replaced by 1,(s′,s′)1 replaced by 0, B′(r′,s′), I′ with (r′,s′)0 replaced by t, C′(r′,s′,t), and I′ with (r′,r′)1 replaced by w′,(s′,r′)0 replaced by x′,(r′,s′)0 replaced by −Ms′v′/d′, and (s′,s′)1 replaced by Mr′v′/d′, D′(r′,s′,v′,d′,w′,x′), MA′(r′,u) multiplies the r′-th column by u, MB(r′,s′) swaps the r′-th column and the s′-th column, MC′(r′,s′,t) adds the r′-th column multiplied by t to the s′-th column, MD′(r′,s′,v′,d′,w′,x′) replaces the r′-th column by the r′-th column multiplied by w′ plus the s′-th column multiplied by x′ and replaces the s′-th column by the r′-th column multiplied by −Ms′v′/d′ plus the s′-th column multiplied by Mr′v′/d′, resulting with (MD′(r′,s′,v′,d′,w′,x′))r′v′=d′ and (MD′(r′,s′,v′,d′,w′,x′))s′v′=0, ∃A′(r′,u)−1(A′(r′,u)−1A′(r′,u)=A′(r′,u)A′(r′,u)−1=I′), ∃B′(r′,s′)−1(B′(r′,s′)−1B(r′,s′)=B′(r′,s′)B′(r′,s′)−1=I′), ∃C′(r′,s′,t)−1(C′(r′,s′,t)−1C′(r′,s′,t)=C′(r′,s′,t)C′(r′,s′,t)−1=I′), and ∃D′(r′,s′,v′,d′,w′,x′)−1(D′(r′,s′,v′,d′,w′,x′)−1D′(r′,s′,v′,d′,w′,x′)=D′(r′,s′,v′,d′,w′,x′)D′(r′,s′,v′,d′,w′,x′)−1=I′).

3: Note


As R is not supposed to be a field, multiplying a row or a column by an arbitrary element of R may not be expressed as an invertible matrix. D(r,s,v,d,w,x) and D′(r′,s′,v′,d′,w′,x′) are introduced in order to make up for that shortcoming: if R was supposed to be a field, any D or D′ operation could be done with A and C or A′ and C′ operations.

This proposition does not claim that those are the only possible operations; those operations are cited for leading M to a Smith normal form.

4: Proof


Hereafter, let us denote the (j,k) component of any matrix, N, as Nkj.

Let us see that A(r,u)M multiplies the r-th row by u.

(A(r,u)M)lj=∑kA(r,u)kjMlk=A(r,u)jjMlj.

When j≠r, =Mlj. When j=r, =uMlr.

That means that only the r-th row is multiplied by u.

Let us see that ∃A(r,u)−1(A(r,u)−1A(r,u)=A(r,u)A(r,u)−1=I).

Let us define A(r,u)−1 as I with (r,r) 1 replaced by u−1.

(A(r,u)−1A(r,u))lj=∑kA(r,u)−1kjA(r,u)lk=A(r,u)−1jjA(r,u)lj. When j≠l, =0. When j=l, =A(r,u)−1jjA(r,u)jj; when j≠r, =11=1; when j=r, =u−1u=1.

So, A(r,u)−1A(r,u)=I.

(A(r,u)A(r,u)−1)lj=∑kA(r,u)kj(A(r,u)−1)lk=A(r,u)jj(A(r,u)−1)lj. When j≠l, =0. When j=l, =A(r,u)jj(A(r,u)−1)jj; when j≠r, =11=1; when j=r, =A(r,u)rr(A(r,u)−1)rr=uu−1=1.

So, A(r,u)A(r,u)−1=I.

Let us see that B(r,s)M swaps the r-th row and the s-th row.

(B(r,s)M)lj=∑kB(r,s)kjMlk.

When j∉{r,s}, =B(r,s)jjMlj=Mlj.

When j=r, =∑kB(r,s)krMlk=Mls.

When j=s, =∑kB(r,s)ksMlk=Mlr.

That means that the r-th row and the s-th row are swapped.

Let us see that ∃B(r,s)−1(B(r,s)−1B(r,s)=B(r,s)B(r,s)−1=I).

Let us define B(r,s)−1:=B(r,s).

(B(r,s)−1B(r,s))lj=∑kB(r,s)kjB(r,s)lk.

When j∉{r,s}, =B(r,s)jjB(r,s)lj=B(r,s)lj=δlj.

When j=r, =∑kB(r,s)krB(r,s)lk=B(r,s)ls, which is 1 when l=r and 0 otherwise.

When j=s, =∑kB(r,s)ksB(r,s)lk=B(r,s)lr, which is 1 when l=s and 0 otherwise.

So, B(r,s)−1B(r,s)=B(r,s)B(r,s)−1=I.

Let us see that C(r,s,t)M adds the r-th row multiplied by t to the s-th row.

(C(r,s,t)M)lj=∑kC(r,s,t)kjMlk.

When j≠s, =∑kC(r,s,t)jjMlj=Mlj.

When j=s, =∑kC(r,s,t)ksMlk=tMlr+Mls.

That means that the r-th row multiplied by t is added to the s-th row.

Let us see that ∃C(r,s,t)−1(C(r,s,t)−1C(r,s,t)=C(r,s,t)C(r,s,t)−1=I).

Let us define C(r,s,t)−1 as I with (s,r) 0 replaced by −t.

(C(r,s,t)−1C(r,s,t))lj=∑k(C(r,s,t)−1)kjC(r,s,t)lk.

When j≠s, =(C(r,s,t)−1)jjC(r,s,t)lj=C(r,s,t)lj=δlj.

When j=s, =∑k(C(r,s,t)−1)ksC(r,s,t)lk=−tC(r,s,t)lr+1C(r,s,t)ls; when l=s, =−t0+11=1; when l=r, =−t1+1t=0; otherwise, =−t0+10=0.

So, C(r,s,t)−1C(r,s,t)=I.

(C(r,s,t)C(r,s,t)−1)lj=∑kC(r,s,t)kj(C(r,s,t)−1)lk.

When j≠s, =C(r,s,t)jj(C(r,s,t)−1)lj=(C(r,s,t)−1)lj=δlj.

When j=s, =∑kC(r,s,t)ks(C(r,s,t)−1)lk=t(C(r,s,t)−1)lr+1(C(r,s,t)−1)ls; when l=s, =t0+11=1; when l=r, =t1+1(−t)=0; otherwise, =t0+0=0.

So, C(r,s,t)C(r,s,t)−1=I.

Let us see that D(r,s,v,d,w,x)M replaces the r-th row by the r-th row multiplied by w plus the s-th row multiplied by x and replaces the s-th row by the r-th row multiplied by −Mvs/d plus the s-th row multiplied by Mvr/d.

(D(r,s,v,d,w,x)M)lj=∑kD(r,s,v,d,w,x)kjMlk.

When j∉{r,s}, =∑kD(r,s,v,d,w,x)jjMlj=Mlj.

When j=r, =∑kD(r,s,v,d,w,x)krMlk=wMlr+xMls. Especially, (D(r,s,v,d,w,x)M)vr=wMvr+xMvs=d.

When j=s, =∑kD(r,s,v,d,w,x)ksMlk=(−Mvs/d)Mlr+(Mvr/d)Mls. Especially, (D(r,s,v,d,w,x)M)vs=(−Mvs/d)Mvr+(Mvr/d)Mvs=0.

That means that the r-th row is replaced by the r-th row multiplied by w plus the s-th row multiplied by x and the s-th row is replaced by the r-th row multiplied by −Mvs/d plus the s-th row multiplied by Mvr/d.

Let us see that ∃D(r,s,v,d,w,x)−1(D(r,s,v,d,w,x)−1D(r,s,v,d,w,x)=D(r,s,v,d,w,x)D(r,s,v,d,w,x)−1=I).

Let us define D(r,s,v,d,w,x)−1 as I with (r,r) 1 replaced by Mvr/d, (r,s) 0 replaced by −x, (s,r) 0 replaced by Mvs/d, and (s,s) 1 replaced by w.

This will be used later: from wMvr+xMvs=d, w(Mvr/d)d+x(Mvs/d)d=(w(Mvr/d)+x(Mvs/d))d=d=1d, which implies that w(Mvr/d)+x(Mvs/d)=1 by the proposition that the cancellation rule holds on any integral domain.

(D(r,s,v,d,w,x)−1D(r,s,v,d,w,x))lj=∑k(D(r,s,v,d,w,x)−1)kjD(r,s,v,d,w,x)lk.

When j∉{r,s}, =∑k(D(r,s,v,d,w,x)−1)jjD(r,s,v,d,w,x)lj=1D(r,s,v,d,w,x)lj=δlj.

When j=r, =∑k(D(r,s,v,d,w,x)−1)krD(r,s,v,d,w,x)lk=(Mvr/d)D(r,s,v,d,w,x)lr+−xD(r,s,v,d,w,x)ls; when l=s, =(Mvr/d)x+−x(Mvr/d)=0; when l=r, =(Mvr/d)w+−x(−Mvs/d)=w(Mvr/d)+x(Mvs/d)=1; otherwise, =(Mvr/d)0+−x0=0.

So, D(r,s,v,d,w,x)−1D(r,s,v,d,w,x)=I.

(D(r,s,v,d,w,x)D(r,s,v,d,w,x)−1)lj=∑kD(r,s,v,d,w,x)kj(D(r,s,v,d,w,x)−1)lk.

When j∉{r,s}, =D(r,s,v,d,w,x)jj(D(r,s,v,d,w,x)−1)lj=1(D(r,s,v,d,w,x)−1)lj=δlj.

When j=r, =∑kD(r,s,v,d,w,x)kr(D(r,s,v,d,w,x)−1)lk=w(D(r,s,v,d,w,x)−1)lr+x(D(r,s,v,d,w,x)−1)ls; when l=s, =w(−x)+xw=0; when l=r, =w(Mvr/d)+x(Mvs/d)=1; otherwise, =w0+x0=0.

So, D(r,s,v,d,w,x)D(r,s,v,d,w,x)−1=I.

Let us see that MA′(r′,u) multiplies the r′-th column by u.

(MA′(r′,u))lj=∑kMkjA′(r′,u)lk=MljA′(r′,u)ll.

When l≠r′, =Mlj. When l=r′, =Mr′ju.

That means that only the r′-th column is multiplied by u.

Let us see that ∃A′(r′,u)−1(A′(r′,u)−1A′(r′,u)=A′(r′,u)A′(r′,u)−1=I′).

Let us define A′(r′,u)−1 as I′ with (r′,r′) 1 replaced by u−1.

A′(r′,u)−1A′(r′,u)=A′(r′,u)A′(r′,u)−1=I′ is the same with the A(r,u) case.

Let us see that MB′(r′,s′) swaps the r′-th column and the s′-th column.

(MB′(r′,s′))lj=∑kMkjB′(r′,s′)lk.

When l∉{r′,s′}, =MljB′(r′,s′)ll=Mlj.

When l=r′, =∑kMkjB′(r′,s′)r′k=Ms′j.

When l=s′, =∑kMkjB′(r′,s′)s′k=Mr′j.

That means that the r′-th column and the s′-th column are swapped.

Let us see that ∃B′(r′,s′)−1(B′(r′,s′)−1B′(r′,s′)=B′(r′,s′)B′(r′,s′)−1=I′).

Let us define B′(r′,s′)−1:=B′(r′,s′).

B′(r′,s′)−1B′(r′,s′)=B′(r′,s′)B′(r′,s′)−1=I′ is the same with the B(r,s) case.

Let us see that MC′(r′,s′,t) adds the r′-th column multiplied by t to the s′-th column.

(MC′(r′,s′,t))lj=∑kMkjC′(r′,s′,t)lk.

When l≠s′, =MljC′(r′,s′,t)ll=Mlj.

When l=s′, =∑kMkjC′(r′,s′,t)s′k=Mr′jt+Ms′j.

That means that the r′-th column multiplied by t is added to the s′-th column.

Let us see that ∃C′(r′,s′,t)−1(C′(r′,s′,t)−1C′(r′,s′,t)=C′(r′,s′,t)C′(r′,s′,t)−1=I′).

Let us define C′(r′,s′,t)−1 as I′ with (r′,s′) 0 replaced by −t.

C′(r′,s′,t)−1C′(r′,s′,t)=C′(r′,s′,t)C′(r′,s′,t)−1=I′ is the same with the C(r,s,t) case.

Let us see that MD′(r′,s′,v′,d′,w′,x′) replaces the r′-th column by the r′-th column multiplied by w′ plus the s′-th column multiplied by x′ and replaces the s′-th column by the r′-th column multiplied by −Ms′v′/d′ plus the s′-th column multiplied by Mr′v′/d′.

(MD′(r′,s′,v′,d′,w′,x′))lj=∑kMkjD′(r′,s′,v′,d′,w′,x′)lk.

When l∉{r′,s′}, =∑kMljD′(r′,s′,v′,d′,w′,x′)ll=Mlj.

When l=r′, =∑k∑kMkjD′(r′,s′,v′,d′,w′,x′)r′k=Mr′jw′+Ms′jx′. Especially, (MD′(r′,s′,v′,d′,w′,x′))r′v′=Mr′v′w′+Ms′v′x′=d′.

When l=s′, =∑kMkjD′(r′,s′,v′,d′,w′,x′)s′k=Mr′j(−Ms′v′/d′)+Ms′j(Mr′v′/d′). Especially, (MD′(r′,s′,v′,d′,w′,x′))s′v′=Mr′v′(−Ms′v′/d′)+Ms′v′(Mr′v′/d′)=0.

That means that the r′-th column is replaced by the r′-th column multiplied by w′ plus the s′-th column multiplied by x′ and the s′-th column is replaced by the r′-th column multiplied by −Ms′v′/d′ plus the s′-th column multiplied by Mr′v′/d′.

Let us see that ∃D′(r′,s′,v′,d′,w′,x′)−1(D′(r′,s′,v′,d′,w′,x′)−1D′(r′,s′,v′,d′,w′,x′)=D′(r′,s′,v′,d′,w′,x′)D′(r′,s′,v′,d′,w′,x′)−1=I′).

Let us define D′(r′,s′,v′,d′,w′,x′)−1 as I′ with (r′,r′) 1 replaced by Mr′v′/d′, (s′,r′) 0 replaced by −x′, (r′,s′) 0 replaced by Ms′v′/d′, and (s′,s′) 1 replaced by w′.

This will be used later: from w′Mr′v′+x′Ms′v′=d′, w′(Mr′v′/d′)d′+x′(Ms′v′/d′)d′=(w′(Mr′v′/d′)+x′(Ms′v′/d′))d′=d′=1d′, which implies that w′(Mr′v′/d′)+x′(Ms′v′/d′)=1 by the proposition that the cancellation rule holds on any integral domain.

(D′(r′,s′,v′,d′,w′,x′)−1D′(r′,s′,v′,d′,w′,x′))lj=∑k(D′(r′,s′,v′,d′,w′,x′)−1)kjD′(r′,s′,v′,d′,w′,x′)lk.

When l∉{r′,s′}, =∑k(D′(r′,s′,v′,d′,w′,x′)−1)ljD′(r′,s′,v′,d′,w′,x′)ll=(D′(r′,s′,v′,d′,w′,x′)−1)lj1=δlj.

When l=r′, =∑k(D′(r′,s′,v′,d′,w′,x′)−1)kjD′(r′,s′,v′,d′,w′,x′)r′k=(D′(r′,s′,v′,d′,w′,x′)−1)r′jw′+(D′(r′,s′,v′,d′,w′,x′)−1)s′jx′; when j=s′, =(−x′)w′+w′x′=0; when j=r′, =(Mr′v′/d′)w′+(Ms′v′/d′)x′=w′(Mr′v′/d′)+x′(Ms′v′/d′)=1; otherwise, =0w′+0x′=0.

So, D′(r′,s′,v′,d′,w′,x′)−1D′(r′,s′,v′,d′,w′,x′)=I′.

(D′(r′,s′,v′,d′,w′,x′)D′(r′,s′,v′,d′,w′,x′)−1)lj=∑kD′(r′,s′,v′,d′,w′,x′)kj(D′(r′,s′,v′,d′,w′,x′)−1)lk.

When l∉{r′,s′}, =D′(r′,s′,v′,d′,w′,x′)lj(D′(r′,s′,v′,d′,w′,x′)−1)ll=D′(r′,s′,v′,d′,w′,x′)lj=δlj.

When l=r′, =∑kD′(r′,s′,v′,d′,w′,x′)kj(D′(r′,s′,v′,d′,w′,x′)−1)r′k=D′(r′,s′,v′,d′,w′,x′)r′j(Mr′v′/d′)+D′(r′,s′,v′,d′,w′,x′)s′j(−x′); when j=s′, =x′(Mr′v′/d′)+(Mr′v′/d′)(−x′)=0; when j=r′, =w′(Mr′v′/d′)+(−Ms′v′/d′)(−x′)=w′(Mr′v′/d′)+x′(Ms′v′/d′)=1; otherwise, =0(Mr′v′/d′)+0(−x′)=0.

So, D′(r′,s′,v′,d′,w′,x′)D′(r′,s′,v′,d′,w′,x′)−1=I′.

References
<The previous article in this series | The table of contents of this series | The next article in this series>
Posted by at
Labels: