# Finding the Appropriate Matrix for a Basis

An abelian group with a basis of $$n$$ elements is called a free abelian group of rank $$n$$. If $$G$$ is free abelian of rank $$n$$ and $$\{x_1, ... ,x_n\},\{y_1, ... ,y_n\}$$ are both bases, then there exist integers $$a_{ij}, b_{ij}$$, such that $$y_i=\sum_ja_{ij}x_j,\; x_i=\sum_jb_{ij}y_j,$$

If we consider the Appropriate Matrices, $$A=(a_{ij}), \; \;B=(b_{ij})$$,it follows that $$AB = I_n$$, the identity matrix.

Now consider the next lemma.

Every subgroup $$H$$ of a free abelian group $$G$$ of rank $$n$$ is free of rank $$s \leq n$$. Moreover there exists a basis $$u_1, ... , u_n$$ for $$G$$ and positive integers $$\alpha_1, ... ,\alpha_s$$ such that $$\alpha_1 u_1, ... , \alpha_s u_s$$ is a basis for $$H$$.

This is Theorem 1.16. in the book Algebraic-Number Theory by Ian Stewart and David Tall, on page 29. The first part of the proof is - In the proof it is written that -

$$u_1, w_2, ... , w_n$$ is another basis for $$G$$. (The appropriate matrix is clearly unimodular.)

QUESTION

If $$G$$ is rank $$n$$, pick any basis $$w_1, ... , w_n$$ of $$G$$ for $$h \in G$$ is of the form, $$h=h_1w_1+ \cdots h_nw_n$$, then what is the appropriate matrix of basis $$w_1, ... , w_n$$ and what is the appropriate matrix of $$u_1, w_2, ... , w_n$$ obtained from for $$u_1=w_1+ q_2w_2 \cdots +q_nw_n$$ ?

MY APPROACH:

Let $$G$$ be a free abelian group of rank $$n$$ with basis $${x_1, ... ,x_n}$$. Suppose $$(a_{ij})$$ is an $$n \times n$$ matrix with integer entries. Then the elements $$y_i= \sum_ja_{ij}x_j$$ form a basis of $$G$$ if and only if $$(a_{ij})$$ is unimodular (Lemma 1.15. on page 28), so the vector of basis, $$(y_i)=\begin{bmatrix} y_{1} \\ y_{2} \\ y_{3} \\ \vdots \\ y_{n} \end{bmatrix} = \begin{bmatrix} a_{11}&a_{12}&\cdots && a_{1n}\\ a_{21}&a_{22}&&&\vdots\\ a_{31} & a_{32} & &a_{3(n-1)}&a_{3n}\\ \vdots & \vdots& & & a_{(n-1)n}\\ a_{n1} & a_{n2} & \cdots &a_{n(n-1)}& a_{nn} \end{bmatrix} \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \vdots \\ x_{n} \end{bmatrix}$$

If $$u_1, w_2, ... , w_n$$ is another basis for $$G$$, then the vector of basis, say $$w_i$$ is,

$$\begin{bmatrix} u_{1} \\ w_{2} \\ w_{3} \\ \vdots \\ w_{n} \end{bmatrix}$$

We want $$a_{ij}$$ for which $$w_i = \sum a_{ij}x_j$$.

Comparing with $$y_i= \sum_ja_{ij}x_j$$, we have $$y_i = w_i$$ for all $$i$$ and $$x_1 = u_1, x_i = w_i$$ for $$i \geq 2$$.

From $$u_1=w_1+q_2 w_2+ \cdots q_n w_n$$, if the associated matrix we get is -

$$(c_{ij})=\begin{bmatrix}1&0&\cdots && 0\\ q_2 &1&\ddots&&\vdots\\ q_3 & 0 & \ddots&0&0\\ \vdots & \vdots& \ddots & \ddots & 0\\ q_n & 0 & \cdots &0& 1 \end{bmatrix},$$

The determinant of a lower triangular matrix is the product of the diagonal entries, in this case this is $$1$$, thus the matrix is unimodular, by the definition of unimodular (see page 28). To verify $$(c_{ij})$$ is the appropriate matrix we do the following calculation:

$$(c_{ij})(x_j)=\begin{bmatrix}1&0&\cdots && 0\\ q_2 &1&\ddots&&\vdots\\ q_3 & 0 & \ddots&0&0\\ \vdots & \vdots& \ddots & \ddots & 0\\ q_n & 0 & \cdots &0& 1 \end{bmatrix} \begin{bmatrix} x_{1} \\ x_{2} \\ x_{3} \\ \vdots \\ x_{n} \end{bmatrix} = \begin{bmatrix} 1 \cdot x_{1} \\ q_2\cdot x_{1}+1 \cdot x_{2} \\ q_3\cdot x_{1}+1 \cdot x_{3} \\ \vdots \\ q_n\cdot x_{1}+1 \cdot x_{n} \end{bmatrix} =\begin{bmatrix} u_{1} \\ w_{2} \\ w_{3} \\ \vdots \\ w_{n} \end{bmatrix}$$

$$\therefore u_1=w_1+q_2 w_2+ \cdots q_n w_n \implies x_1 = x_1(q_2+q_3+ \cdots q_n) + x_2+x_3 \cdots x_n$$

$$\implies 0 = x_1(-1+q_2+q_3+ \cdots q_n) + x_2+x_3 \cdots x_n$$.

If $$(-1+q_2+q_3+ \cdots q_n)=0$$ then the set $$\{ x_2, x_3 \cdots x_n \}$$ is not a basis by the definition of basis since $$0 = x_2+x_3 \cdots x_n$$ means one of the element of $$\{ x_2, x_3 \cdots x_n \}$$ is depended on others. Thus the super-set $$\{ x_1, x_2, x_3 \cdots x_n \}$$ can not be basis either.

If $$(-1+q_2+q_3+ \cdots q_n)\neq 0$$ then the set $$\{ x_1, x_2, x_3 \cdots x_n \}$$ is not a basis by the definition of basis since $$0 = x_1+x_2+x_3 \cdots x_n$$ means one of the element of $$\{x_1, x_2, x_3 \cdots x_n \}$$ is depended on others.

Thus, $$(c_{ij})$$ can not be the appropriate matrix because then $$\{ x_1, x_2, x_3 \cdots x_n \}$$ is not a basis which is against the hypothesis.

The basis $$w_1,w_2,\dots,w_n$$ is changed to a basis $$u_1,w_2,\dots,w_n$$ where $$u_1 = w_1 + q_2 w_2 + \dots + q_n w_n.$$ This might be written as $$\begin{bmatrix} u_1 \\ w_2 \\ \vdots \\ w_n\end{bmatrix} = \begin{bmatrix} 1 & q_2 & \dots & q_n \\ & 1 \\ & & \ddots \\ & & & 1 \end{bmatrix} \begin{bmatrix} w_1 \\ w_2 \\ \vdots \\ w_n\end{bmatrix}.$$ The other way around is obtained by inverting this matrix or noting that $$w_1 = u_1 - q_2 w_2 - \dots - q_n w_n.$$ We obtain $$\begin{bmatrix} w_1 \\ w_2 \\ \vdots \\ w_n\end{bmatrix} = \begin{bmatrix} 1 & -q_2 & \dots & -q_n \\ & 1 \\ & & \ddots \\ & & & 1 \end{bmatrix} \begin{bmatrix} u_1 \\ w_2 \\ \vdots \\ w_n\end{bmatrix}.$$ These two are the appropriate unimodular matrices for the basis changes between $$w_1,w_2,\dots,w_n$$ and $$u_1,w_2,\dots,w_n$$.