4

In the book of Linear Algebra by Werner Greub at page 96, it is given that;

The elementary transformations on a matrix are:

(1.1.) Interchange of two vectors $X_i$ and $X_j(i\not =j).$

(1.2.) Interchange of two vectors $Y_k$ and $Y_l(k\not =).$

(11.1.) Adding to a vector $X_i$ an arbitrary multiple of a vector xj(j\not =i).

(11.2.) Adding to a vector $Y_k$ an arbitrary multiple of a vector $Y_l (l \not = k)$.

It is easy to see that the four above transformations have the following effect on the matrix $M (\phi)$:

(1.1.) Interchange of the rows i and j.

(1.2.) Interchange of the columns k and I.

(11.1.) Replacement of the row-vector $a_i$ by $a_i+$ $\lambda a_j(j\not =i).$

(11.2.) Replacement of the column-vector $b_k$ by $b_k+\lambda b_l(l\not=k).$

I have no problem in understanding the operations, but what I'm asking is that what do those operations preserve, especially, in the view that they are matrix representations of linear mappings of vector spaces ?

For example, though I haven't studied in details, in Gaussian elimination, basically we are applying these elementary transformations to the coefficient matrix of a system of equations, and in the book, it says that after those operations, the given system is equivalent to the old one. I don't know how because I don't know what the transformations do and do not preserve when we applied them to a matrix.

Another example, in 11.2 when we add $\lambda b_l$ to the kth row, $\phi$ maps the kth bases to $\phi_{old} (x_k) + \lambda \phi (x_l)$, so the image has change, hence the map has changed, at least according to me.

Edit:

For those who stumbled with these elementary transformation as I was, please see this question for insight.

Community
  • 1
Our
  • 7,285
  • The elementary transformations you describe (a combination of elementary row operations and elementary column operations) do "change the map that the matrix is describing" when we consider the matrix as representing the map with respect to a fixed ordered basis for both input and output. However these operations might be accompanied by changes to the bases (in the input and output) to leave the map represented thereby unchanged. – hardmath Jun 27 '17 at 16:00
  • @hardmath the book doesn't change the basis at all. – Our Jun 27 '17 at 16:07
  • Hmm, curious. In that case the changes to the matrix will clearly change the map. For example, suppose the matrix is $(1; 1)$ and we apply an elementary column operation to get $(1; 0)$. Given the standard bases (say) for the "input" vector space $\mathbb{R}^2$ and "output" vector space $\mathbb{R}$, these are clearly different maps (though they are both of rank one). – hardmath Jun 27 '17 at 16:11
  • @hardmath also see my edit. – Our Jun 27 '17 at 16:12
  • See the setup paragraph immediately preceding in the book on page 95. What is being described in the original top portion of the highlighted material are elementary basis-transformations, and the effects on the matrix are correspondingly stated in the bottom portion of that material. – hardmath Jun 27 '17 at 16:20
  • @hardmath I'm look to that page right now, and don't see anything related with that.I have put a link to the question of the book, I'm using the forth edition of the book. – Our Jun 27 '17 at 16:28
  • 2
    Re: elimination, you have to be a bit careful here. In general, two matrices are equivalent precisely if they represent the same linear transformation with respect to different domain and codomain bases. Gaussian elimination only deals with elementary row operations, which means that only the codomain basis changes. For an explicit example with a linear system in $\mathbb{R}^2$, the equation $x = 0$ is not equivalent to $x+y = 0$ (their matrices are not row-equivalent), however their matrices are equivalent if you also allow column operations (i.e. both matrices have rank 1). – Alex Provost Jun 28 '17 at 16:55
  • 2
    Elementary matrices are involved here https://en.wikipedia.org/wiki/Elementary_matrix, you can study forms of their products to obtain what is preserved, for example interchanging rows preserves absolute value of determinant, the most general property which is preserved is matrix non-singularity – Widawensen Apr 15 '18 at 10:33
  • @Widawensen Meaning that the matrix is non-singular iff its transformed form is also non-singular ? – Our Apr 16 '18 at 04:07
  • @onurcanbektas Yes, I think so. – Widawensen Apr 16 '18 at 10:35

1 Answers1

1

Let $A\in M_{n,p}$ with $rank(A)=r$. Note that (1.1) and (11.1) are associated to a left multiplication by an elementary matrix and (1.2), (11.2) to a right one. If we choose correctly these elementary transformations, then we obtain an equivalence of matrices (cf. @Alex Provost 's post) in the form

$P_k\cdots P_1AQ_1\cdots Q_l=\begin{pmatrix}D&0_{n-r,r}\\0_{r,p-r}&0_{n-r,p-r}\end{pmatrix}$ where $D=diag(a_1,\cdots,a_r)$, $a_i\not= 0$, that is

$PAQ=\begin{pmatrix}D&0_{n-r,r}\\0_{r,p-r}&0_{n-r,p-r}\end{pmatrix}$ where $P\in GL_n,Q\in GL_p$ have determinant $\pm 1$.

Then one changes the bases of the domain and of the codomain. That permits to obtain $r$; of course, that does not give the eigenvalues of $A$.

If $n=p=r$, then we obtain $\det(A)=\pm a_1\cdots a_n$ and $A^{-1}$ as follows: $A^{-1}=Q_1\cdots Q_lD^{-1}P_k\cdots P_1$.

  • So, we can check whether $A$ is invertible or not by by checking whether it can be written as a diagonal matrix $(p=r)$ using both row/column operation ? – Our Apr 16 '18 at 04:05
  • Since, the determinant of $A$ is non-zero iff the determinant of $PAQ$ is non-zero, as @ Widawensen pointed out, the non-singularity has to be preserved, right ? – Our Apr 16 '18 at 04:12
  • 1
    @onurcanbektas , the rank of any square or non-square matrix is preserved and all the calculations are in the underlying field. Moreover, if $n=p=r$, then one can recover $\det(A),A^{-1}$ with complexity $O(n^3)$; indeed, there are $O(n^2)$ matrices $(P_i,Q_j)$ and each product by such a matrix is in $O(n)$. –  Apr 16 '18 at 11:08