[UnSA] An Integers Matrix Lemma that sometimes being forgotten

[UnSA] An Integers Matrix Lemma that sometimes being forgotten

21:53:00   UnSA,

I am going to prove the following useful lemma and wrapping the proof of inverse-adjugate formula inside my proof. I hope I put enough details on it.

Lemma
Let $A\in \mathbb{Z}^{n\times n}$ with $\text{det } A \neq 0$. Then there exists a unique matriks $B\in \mathbb{Q}^{n\times n}$ such that $AB=BA=(\text{det } A) I$, and moreover $B$ has integer entries.

Proof:
Suppose that $A=(a_{ij})$, where $a_{ij}\in \mathbb{Z}$. Let $C_{ij}$ denotes the $(i,j)$ cofactor of $A$, that is $C_{ij}=(-1)^{i+j}M_{ij}$ where $M_{ij}$ is the determinant of the $(n-1) \times (n-1)$ matrix obtained by deleting the $i$-th row and $j$-th column of $A$. Since $A$ has integers entries, $M_{ij}$ is the determinant of a matrix with integers entries, thus $M_{ij}$ is also an integer for all $i,j \in \{1,2,\cdots,n\}$.  So we have $C_{ij} \in \mathbb{Z}$ for all $i,j\in\{1,2,\cdots,n\}$.

Define the matrix $C=(C_{ij})$, that is the $ij$-th entry of $C$ is $C_{ij}$, and let $B=C^{T}$. Since all $C_{ij}$ are integers,  we conclude that $B$ has integer entries.

Next we try to compute $AB$. Denote the $ij$-th entry of $AB$ by $z_{ij}$, therefore by the rule of multiplication of matrix we have
\[z_{ij}=\sum_{k=1}^n a_{ik} C_{jk}\]
If $i=j$ then by cofactor expansion for determinant of $A$ we have
\[z_{ii}=\sum_{k=1}^n a_{ik} C_{ik}= \text{det } A\]
If $i\neq j$, consider the matrix
\[A_{ij}=\left(\begin{array}{ccccc} a_{11} &a_{12} &\cdots &\cdots &a_{1n}\\ \vdots &\vdots &\vdots &\vdots &\vdots \\ a_{i1} &a_{i2} &\cdots &\cdots &a_{in} \\ \vdots &\vdots &\vdots &\vdots &\vdots \\  a_{i1} &a_{i2} &\cdots &\cdots &a_{in} \\ \vdots &\vdots &\vdots &\vdots &\vdots \\ a_{n1} &a_{n2} &\cdots &\cdots &a_{nn}\end{array}\right)\]
here is the explanation of the above matrix, the two identical rows are the $i$-th row and the $j$-th row, and since we have these two identical rows, the determinant of this new matrix is zero. Also we have $C_{jk}(A_{ij})=C_{jk}$, that is the cofactor of $A_{ij}$ amongst $j$-th row is the same as the cofactor of $A$ amongst $j$-th row. Using these facts and cofactor expansion, for $i\neq j$ we have
\[0=\text{det }(A_{ij})=\sum_{k=1}^n a_{ik} C_{jk}(A_{ij})=\sum_{k=1}^n a_{ik} C_{jk}=z_{ij}\]
We conclude that
\[z_{ij} = \left\{ \begin{array}\text{det } A & i= j \\ 0 & i\neq j \end{array}\right.\]

and we have managed to prove that $AB=(\text{det } A) I$, where $B$ has integer entries. Now, since $\text{det } (A) \neq 0$ the inverse matrix $A^{-1}$ exists, thus
\[\begin{align*}AB=(\text{det } A) I &\Rightarrow ABA= (\text{det } A)IA=A (\text{det } A) \\ &\Rightarrow A^{-1}A(BA)=A^{-1}A(\text{det } A) \end{align*}\]
so that we have $BA=(\text{det } A) I$ as well. It remains to prove that $B$ is unique.
Suppose there exists $B_1\neq B$ such that $AB_1 = B_1A= (\text{det } A) I$. Therefore \[AB_1 = (\text{det } A) I = AB\]
multiplying both sides by $A^{-1}$ we have $B_1=B$, a contradiction, thus $B$ is unique and we are done.

One Corollary that follows from this lemma is:
The inverse of the integer matrix with determinant equals $+1$ or $-1$ is again the integer matrix.

[sometimes we just forgot we have this fact]

Continue Reading

[Eksplorasi] Soal 1 hari pertama ON MIPA 2011

[Eksplorasi] Soal 1 hari pertama ON MIPA 2011

08:20:00   Olimpiade Matematika, ON MIPA, Univ,

Soal berikut adalah soal ON MIPA tahun 2010 hari pertama soal nomor 1 [dapet dari blog Raja Oktovin ]
Saya tidak hanya akan mencoba membahas soal ini (tapi sedikit memodifikasi/memberi komentar yang berhubungan dengan soalnya, dan akan saya lakukan untuk soal-soal yang lain :D)

Soal 1.  Misalkan $N$ adalah subgroup berhingga dari $G$. Misalkan $G=\langle T \rangle$ dan $N=\langle S \rangle$ dimana $S,T \subseteq G$. Buktikan bahwa $N$ subgroup normal jika dan hanya jika $tSt^{-1} \subseteq N$ untuk setiap $t\in T$.Gunakan definisi: $\langle X \rangle = \{x_1x_2\cdots x_n | x_i \in X\}$

Solusi:
$\Rightarrow$ Misalkan $N$ subgroup normal, maka untuk setiap $s \in S$ diperoleh $s\in N$ sehingga $g s g^{-1} \in N$ untuk setiap $g\in G$, secara khusus karena $T\subset G$ diperoleh $tst^{-1} \in N$ untuk setiap $t\in T$, diperoleh $tSt^{-1} \in N$.

$\Leftarrow$ Misalkan $tSt^{-1} \subseteq N$ untuk setiap $t\in T$. Ambil sebarang $n \in N$ dan sebarang $g\in G$, maka $$n=s_1 s_2 \cdots s_k \qquad g=t_1t_2\cdots t_l$$ dimana $s_i \in S$ dan $t_i\in T$.
Jadi
\begin{align*}gng^{-1} &= \prod_{i=1}^l t_i \prod_{i=1}^k s_i \prod_{i=1}^l t_{l-i+1}^{-1}\\
&= \prod_{i=1}^{l-1}t_i \left(\prod_{j=1}^k t_l s_j t_l^{-1}\right) \prod_{i=2}^l t_{l-i+1}^{-1}
\end{align*}

Berdasarkan sifat tertutup dari $N$ dan karena $t_l s_j t_l^{-1} \in N$ maka  $\left(\prod_{j=1}^k t_l s_j t_l^{-1}\right) \in N$. Sehingga $\prod_{j=1}^k t_l s_j t_l^{-1} = \prod_{i=1}^{k_1} s_i^{(1)}$ dimana $s_i^{(1)}\in S$. Jadi
\begin{align*}
gng^{-1}=\prod_{i=1}^{l-1}t_i \prod_{i=1}^{k_1} s_i^{(1)} \prod_{i=2}^l t_{l-i+1}^{-1}
\end{align*}

Pada perkalian diatas, banyak suku $t_i$ sudah berkurang sebuah. Dengan cara yang serupa, kita dapat mengurangi jumlah suku dari $\prod_{i=1}^{l-1}t_i$  dan $\prod_{i=2}^l t_{l-i+1}^{-1}$ sehingga setelah $l-1$ kali kita peroleh

\[gng^{-1}=t_1 \prod_{i=1}^{k_{l-1}} s_i^{(l-1)} t_1^{-1} = \prod_{i=1}^{k_{l-1}} (t_1 s_i^{(l-1)}t_1^{-1}) \in N\]
terbukti.

Modifikasi

Karena notasi $\langle X \rangle$ biasanya digunakan untuk subgroup terkecil yang memuat $X$, yaitu
\[\langle X \rangle := \bigcap \{H : X \subseteq H \text{ dan $H$ adalah subgroup dari $G$} \} \]
Irisan dari semua subgroup dari $G$ yang memuat $X$.
Definisi ini adalah yang umum digunakan untuk $\langle X \rangle$. Jelas bahwa $X\subseteq \langle X\rangle$, dan apabila $H$ adalah sebarang subgrup yang memuat $X$ maka $\langle X \rangle \subseteq H$.

Cukup natural apabila juga dipertanyakan:

Apabila definisi $\langle X \rangle$ diganti menjadi subgroup terkecil yang memuat $X$, apakah soal tetap benar?

Jawabannya : tidak selalu, lihat counterexample dibawah.

Soal 1 (Modifikasi Pertama).  Misalkan $G$ adalah grup berhingga dan $N$ adalah subgroup dari $G$. Misalkan $G=\langle T \rangle$ dan $N=\langle S \rangle$ dimana $S,T \subseteq G$. Buktikan bahwa $N$ subgroup normal jika dan hanya jika $tSt^{-1} \subseteq N$ untuk setiap $t\in T$.$\langle X \rangle$ adalah subgroup terkecil dari $G$ yang memuat $X$.

Soal 1 (Modifikasi Kedua).  Misalkan $N$ adalah subgroup berhingga dari $G$. Misalkan $G=\langle T \rangle$ dimana $T \subseteq G$. Buktikan bahwa $N$ subgroup normal jika dan hanya jika $tNt^{-1} \subseteq N$ untuk setiap $t\in T$.

$\langle X \rangle$ adalah subgroup terkecil dari $G$ yang memuat $X$.

Pembuktian dari  kiri ke kanan, similar. Jadi berikutnya kita hanya akan membuktikan dari kanan ke kiri. Berikut adalah sebuah lemma yang berkaitan dengan $\langle X \rangle$

(Lemma 1)  Untuk $\langle X \rangle$ adalah subgrup terkecil dari $G$ yang memuat $X$ maka anggota-anggota di $\langle X\rangle$ berbentuk : \[x_1x_2 \cdots x_v\] dimana $x_i \in X$ atau $x_i^{-1}\in X$.

Bukti: 
Misalkan $S$ adalah himpunan yang memuat hasil kali  yang berbentuk $x_1 x_2 \cdots x_v$ dengan $x_i \in X$ atau $x_i^{-1}\in X$. Pertama-tama, kita buktikan bahwa $S$ adalah subgroup dari $G$. Perhatikan bahwa jika $d=x_1 x_2 \cdots x_v$ dan $e=x_1^{\prime} x_2^{\prime} \cdots x_u^{\prime}$ dimana $x_i, x_i^{\prime} \in X$ atau $x_i^{-1},{x_i^{\prime}}^{-1} \in X$
maka
\[de=x_1 x_2 \cdots x_v x_1^{\prime} x_2^{\prime} \cdots x_u^{\prime} \]
jelas memenuhi syarat sebagai anggota $S$, jadi $S$ tertutup.  Kemudian $d^{-1}=x_v^{-1}\cdots x_2^{-1}x_1^{-1}$ memenuhi $x_i^{-1}\in X$ atau $x_i = (x_i^{-1})^{-1} \in X$, sehingga $S$ memenuhi sifat inverse. Jadi $S$ adalah subgroup dari $G$.

Kemudian karena $X \subset S$, maka $S$ adalah suatu subgroup yang memuat $X$, hal ini menyebabkan $\langle X \rangle \subset S$. Kemudian untuk sebarang $s \in S$, maka $s$ adalah perkalian dari anggota-anggota $X$ atau yang inverse nya ada di $X$, yakni $s$ adalah perkalian dari anggota-anggota yang berada di $\langle X \rangle$, karena $\langle X\rangle$ tertutup terhadap perkalian maka $s\in \langle X \rangle$, jadi $S=\langle X\rangle$.

Apabila $G$ grup berhingga maka  $\langle X\rangle$ yang ada di ON MIPA sama dengan yang di Lemma 1.

(Lemma 2)  Apabila $G$ adalah grup berhingga, maka $\langle X \rangle= \{x_1x_2\cdots x_v | x_i \in X\}$ (definisi yang sama dengan soal di ON MIPA)

Bukti : 
Perhatikan bahwa dengan cara yang sama seperti bukti sebelumnya himpunan $S=\{x_1x_2\cdots x_v | x_i \in X\}$ tertutup terhadap operasi pada $G$, dan karena $G$ berhingga, maka $S$ adalah subgroup. Dengan cara yang sama seperti bukti sebelum nya diperoleh $\langle X \rangle=S$.

Dengan Lemma 2 ini, soal modifikasi pertama berubah menjadi soal ON MIPA, dengan demikian soal selesai.

Apabila $G$ tidak berhingga, maka soal modifikasi pertama tersebut salah. Counterexample (diberikan oleh Arturo Magidin)

$G=\langle S \cup \{x\}\rangle$ dimana  $S=\left\{\left.\left(\begin{array}{cc}1 & m\\ 0 & 1\end{array}\right)\in G\ \right|\ m\in\mathbb{Z}\right\}$ dan $x = \left(\begin{array}{cc} 2 & 0\\ 0 & 1\end{array}\right).$ Pada kasus ini $N=S$ dan $tNt^{-1} \subset N$ namun $N$ tidak normal di $G$, karena $x^{-1}\left(\begin{array}{cc}1 & 1\\ 0 & 1\end{array}\right)x \not\in N$.

Untuk soal 1 modifikasi kedua,  kita gunakan Lemma berikut:

(Lemma 3)  Jika $G=\langle T \rangle$ dan $N$ adalah subgroup dari $G$ yang memenuhi $tNt^{-1} = N$ maka $N$ adalah subgroup normal.

Bukti :
Ambil sebarang $g\in G$, maka
\[g=t_1t_2\cdots t_k\]
dimana $t_i\in T$ atau $t_i^{-1}\in T$. Dari hipotesis diperoleh $tNt^{-1}$ mengakibatkan $t^{-1}Nt=N$, jadi untuk setiap $t_i$ (tidak harus di $T$ asalkan inverse nya di $T$) berlaku $t_iNt_i^{-1}=N$. Sehingga untuk setiap $n \in N$ diperoleh
\[gng^{-1}= t_1t_2\cdots \underbrace{(t_k n t_k^{-1})}_{\in N} \cdots t_1^{-1} \in N.\]
Jadi $N$ adalah subgroup normal.

Untuk $N$ subgrup berhingga, maka $t^{-1}Nt \subset N$ akan menyebabkan $t^{-1} Nt = N$ (Bukti untuk fakta ini hampir selalu ada di setiap buku aljabar abstract yang membahas subgroup normal).

Sehingga dengan Lemma 3 dan karena $N$ subgrup berhingga soal 1 modifikasi kedua selesai :D

Continue Reading

Why do authors usually mix the "isomorphic" and "equal" on sign?

Why do authors usually mix the "isomorphic" and "equal" on sign?

23:47:00  

A global use of the "$A=B$"  is to denote that object $A$ is identical with object $B$. In the set theory this means that $A$ and $B$ have the same elements. But, frequently in some of Papers about Algebraic-Structure  we see some propositions like the following:

1. [Abelian p-group $H_p$ as the product of p-cyclic group]
\[H_p = (\mathbb{Z}/p^{e_1}\mathbb{Z}) \times (\mathbb{Z}/p^{e_2}\mathbb{Z}) \times \cdots \times (\mathbb{Z}/p^{e_r}\mathbb{Z}) \]

2. [Projectional result Linear Functional $f:A \rightarrow \mathbb{C}$, where $A$ is $n$-dimensional vector space for $n\geq 2$]

\[A = \text{ker} (f) \oplus \mathbb{C}\]


Those propositions don't make any sense if we think "=" as equal sign. For the first proposition implies that any abelian p-group no matter how strange its elements is, can be described as the well-known product of modulo $p^{e_i}$ integers.
The second proposition is even more confusing, since $A$ can be any abstract vector space and hence $\text{ker} (f)$ is also an abstract vector space, we can't even "add" the element of $A$ with the element of  $\mathbb{C}$.

We can think the "=" as isomorphic on both propositions and the problem is solved, but occasionally in the same paper/book the Authors use "$\cong$" and they often mix it with "$=$".  Depending on the focus of the paper or book  this might not be a serious problem, for example in the paper about group structure it is safe to think isomorphic as "the same".

Consider you are being asked by someone who bother the difference between "$=$" and "$\cong$", he asks you about the statement of Fundamental Theorem of Finite Abelian Group which states that :
Every Finite Abelian Group is the direct product of its cyclic subgroups.

Suppose he tested you with a challenge, he gave you a finite abelian group $G$, and want you to verified the statement of above theorem.

Suppose that you're given a finite abelian group $G$ and then you want to find the sets $A_1,A_2,\cdots,A_k$ which are cyclic subgroups of $G$, so that every $x \in G$ satisfies $x= a_1 a_2 \cdots a_k$ where $a_i \in A_i$. Yes Of Course, by Fundamental Theorem of Finite Abelian Group we can always do this,
for example if $G=\{e,a,b,ab\}$ where $a^2=b^2=e$ then we can take $A_1 = \{e, a\}$, $A_2\{e,b\}$ and $A_3=\{e,ab\}$, therefore $A_1 A_2 A_3 = G$.
Note that here we take an internal product, since for the case of  $G$ is abelian group every subgroup of $G$ is a normal subgroup, hence the external direct product implies the internal direct product (note that $A_i \cap A_j = \{e\}$).

We can also "cheat the someone" since he/she doesn't give us a proper form of $G$, we can start the "cheat" by first stating that:
"I let $G=\{(0,0,0), (a_1,b_1,c_1), (a_2,b_2,c_2),\cdots, (a_n,b_n,c_n) \}$, since you don't give me the exact form of $G$, I must name its elements by something, and I choose to name them by these variables". And then, we pretend that we first know nothing about $a_i,b_i$, and $c_i$ (that we just want to name them that way) and it turns out that it is not our fault then
$\{(0,0,0),(a_1,0,0) ,(a_2,0,0),\cdots,(a_n,0,0)\}$,
$\{(0,0,0), (0,b_1,0),(0,b_2,0),\cdots,(0,b_n,0)\}$ and
$\{(0,0,0),(0,0,c_1),(0,0,c_2),\cdots,(0,0,c_n)\}$
are all become cyclic group :D (Of course we already know that they will).

But according to proposition 1, $\mathbb{Z}/p^{e_i} \mathbb{Z}$ is not always a subgroup of $H_p$, they have different elements. We still can resolve it like when we "cheat"above by stating that the elements of $H_p$ are $(h_1,\cdots,h_r)$.

Suppose that someone is one step ahead, he/she asks you by first giving the exact element of $H_p$, say $H_p$ is abelian group of order $8$ given by $\{e,a_2,\cdots,a_8\}$, to make it a non-cyclic group (after some calculations or cayley table) $H_p=\{e, a_1, a_2, a_1a_2, b_1,a_1b_1, a_2b_1, a_1a_2b_1\}$  and $a_2^2=e$, $a_1^2=a_2$, $b_1^2=e$, and $a_i b_j = b_j a_i$ (he/she should agree with these, since this is an effort to make $H_p$ a non-cyclic abelian group of order 8, yes there might be other way).  Since $a_1^2=a_2$, $H_p$ depends only on $a_1$ and $b_1$, so we can name  $a=a_1$ and $b=b_1$ and hence
\[H_p = \{e,a,a^2,a^3,b,ab,a^2b\}\]

Do you realize? we've just stated
$$\{e,a_2,\cdots,a_8\}= \{e, a_1, a_2, a_1a_2, b_1,a_1b_1, a_2b_1, a_1a_2b_1\} = \{e,a,a^2,a^3,b,ab,a^2b\}$$

and we seem okay, though we throw $a_8$, $a_4$, $b_2$ etc. And we feel fine about that. We stated the three sets are the same, even though they are virtually not have the same elements. That's because we agree $a_1$ is $a$ and $b_1$ is $b$, and $a_2$ is $a_1^2$ and so on..

We agree! That is important in Mathematics.

Back on, what is actually "$=$" on proposition 1 and 2 ? In general it is isomorphism sign.
With some agreement, we can make it equal sign
(You know not everyone on this world use symbol $2$ to denote "two", in ancient roman its "II", in arabic it's different also, but are they really different in meaning?  no, even sounded different in many languages, two is always two :D )

Hello formalism? :D :D

Continue Reading