1
$\begingroup$

When I implement a Gauss-Jordan algorithm I can either have a 1 column result matrix or a multi-column result matrix (I mean the right hand side of the augmented matrix). The first case would be the one for linear systems of equations and the latter case would come into play when calculating the inverse of the source matrix.

Now I want to use full-pivoting with both row- and column-swapping. When I swap two rows in the source matrix I swap the same two rows in the result matrix as well.

What I don't get and couldn't find is how a column swap affects the result matrix. I can't really swap columns in the case of a single-column matrix. This would only work if the result matrix had the same amount of columns as the source matrix.

Could someone explain to me, how this is treated? I could only find examples for matrix inversion using partial pivoting, in which case this problem does not arise.

$\endgroup$
3
$\begingroup$

Row (Column) reducing a matrix is essentially a process whereby you do a series of elementary operations, which when taken together has the same effect as multiplying your equation (augmented system) by an invertible matrix (which is a product of elementary operations - row or column).

Now the distinction between a row operation and a column operation, is that a row operation is the same as multiplying on the left, eg $E_RA=E_RB$ whereas a column operation is the same as multiplying on the right, eg $AE_C=BE_C$. To be able to do any such an operation on an augmented system $[A : B]$ you must have that $A$ and $B$ have the same amount of rows (columns) for a row operation (column operation). So you cannot for example perform a column operation on an augmented system of $Ax=B$ where $A$ has multiple columns, and $B$ only one - within the context of solving the system for $x$ such an operation would be the same as trying to multiply $A$ and $B$ on the right with some elementary matrix - and the multiplication will be undefined for one of these matrices since they do not have the same amount of columns.

Now, just as you can row reduce the augmented system $[A : I]$ to $[I : A^{-1}]$ (if $A$ is invertible) you can also column reduce $\begin{bmatrix} A \\ \hline \\ I \end{bmatrix}$ to $\begin{bmatrix} I \\ \hline \\ A^{-1} \end{bmatrix}$. The use of augmenting with $I$ is that it allows you to retrieve the composition of elementary operations as a single invertible matrix.

What about both row and column operations on a matrix? Here the second observation I want to make, is that the whole point of augmenting and row or column reducing together, is that instead of multiplying one matrix and then the other with the same elementary matrix you do it all together in one step, but usually in the end (if you are not solving a linear system) you want to retrieve the nonsingular matrices composed of the series of elementary operations. So you want $P$ and/or $Q$ so that $PAQ$ is some meaningful equivalent matrix. Consider reducing

$\begin{bmatrix}A & I \\ I & 0 \end{bmatrix}$ to $\begin{bmatrix}B & P \\ Q & 0 \end{bmatrix}.$

(A needn't be square, but then the two identity submatrices are not the same size). What this means is that $PAQ=B$ and we say that $A$ and $B$ are equivalent.

If $A$ is invertible then you can also use both row and column operations:

Reduce $\begin{bmatrix}A & I \\ I & 0 \end{bmatrix}$ to $\begin{bmatrix}I & P \\ Q & 0 \end{bmatrix}.$

What this means is $PAQ=I$, so that $A^{-1}=QP$.

The one exception I need to mention where one can use both row and column operations on an augmented system $[A : I]$ is where $A$ is a symmetric and you reduce to $[D : Q^T]$ by doing a series of alternating column and row operations (column operation followed by exactly the same row operation, eg swap column 1 and 2 followed by swap row 1 and 2). Then in the end you will have $D=Q^TAQ$. Of course this only works because $A$ is symmetric.

$\endgroup$
  • $\begingroup$ Thank you, Christiaan, for your answer. I got out of it that I can only use column swapping when the result matrix has as many columns as the source matrix. But I don't get what I'm supposed to do on a column swap in the source matrix. Say both are 3x3 matrizes. I swap column 2 and 3 in the source matrix: What happens to the result matrix in that case? Do I swap these columns there as well? $\endgroup$ – Jens Apr 8 '14 at 8:47
  • $\begingroup$ Yes, you must then swap the same columns in the result matrix too. in effect you then get as end result: $PAQ$ and $PBQ$ for the augmented system $[A : B]$. But the relationship between them is then dependent on the context. why do you want to do this? $\endgroup$ – Christiaan Hattingh Apr 8 '14 at 10:00
  • 1
    $\begingroup$ ok - I read your question again - sorry my answer is perhaps too detailed. To use full pivoting to find an inverse you must do the following: Reduce $\begin{bmatrix}A & I \\ I & 0 \end{bmatrix}$ to $\begin{bmatrix}I & P \\ Q & 0 \end{bmatrix}.$ What this means is $PAQ=I$, so that $A^{-1}=QP$. $\endgroup$ – Christiaan Hattingh Apr 8 '14 at 10:32
  • 1
    $\begingroup$ so row operations only affect the matrix on the right and column operations the matrix below...then you must still calculate the product $QP$ which equals $A^{-1}$. $\endgroup$ – Christiaan Hattingh Apr 8 '14 at 10:34
  • $\begingroup$ Ah I see, I need two result matrizes for full pivoting then. Thank you I will try that and will then accept your answer. $\endgroup$ – Jens Apr 8 '14 at 11:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.