Is it allowed to swap 2 columns in gaussian elimination?

Question

I am trying to find inverse of a matrix I know swapping two rows is fine but what about columns ?

Answer 1

Think about your algorithm like this: you start with your double-matrix $(A\mid I)$, and you're to end up with $(I\mid A^{-1})$. Every time you do an operation on the rows of $(A_n\mid B_n)$, you end up with $(A_{n+1}\mid B_{n+1})=(P_{n}A_n\mid P_nB_n)$ for some invertible matrix $P_n$ that depends on the operation you've done. In the end, you'll end up with $(I\mid S)=(P_NP_{N-1}\cdots P_0A\mid P_NP_{N-1}\cdots P_0)$, at which point you'll need to realise that, since $(P_N\cdots P_0)A=I$, then $S=P_N\cdots P_0=A^{-1}$.

Likewise, every time you do an operation on the columns of both matrices - by which I mean, for instance, that you can't swap a column of $A_n$ with a column of $B_n$ and, if you swap the first and second columns of $A_n$, then you must swap the first and second columns of $B_n$ too - you're doing a step like $$(A_n\mid B_n)\mapsto (A_{n+1}\mid B_{n+1})=(A_nQ_n\mid B_nQ_n)$$ where, again, $Q_n$ depends on the move you're doing. If you only do column operations, then you'll eventually end up with $(I\mid T)=(AQ_0\cdots Q_N\mid Q_0\cdots Q_N)$, which again implies that $T=A^{-1}$.

However, if you start mixing the two, what you end up with is an identity in the form $$(I\mid U)=(P_{k_0}\cdots P_{k_t}AQ_{h_0}\cdots Q_{h_r}\mid P_{k_0}\cdots P_{k_t}Q_{h_0}\cdots Q_{h_r})$$ which, in principle and in point of fact, does not establish an immediate relationship between $U$ and $A^{-1}$.

So the short answer is: you must decide beforehand if you want to perform the algorithm to calculate $A^{-1}$ by eliminating the rows or the columns and stick to your choice. Either works, but not the two together.

Answer 2

Swapping columns is fine, provided you take note that the two corresponding unknowns are swapped as well.

$$\begin{cases}ax&+&b\,\,y&+&c\,\,z=&d\\a'x&+&b'\,y&+&c'\,z=&d'\\a''x&+&b''y&+&c''z=&d''\end{cases}$$ is equivalent to

$$\begin{cases}a\,\,x&+&c\,\,z&+&b\,\,y=&d\\a'\,x&+&c'\,z&+&b'\,y=&d'\\a''x&+&c''z&+&b''y=&d''.\end{cases}$$

If you are working with a full $[A|I]$ decomposition, you will need to permute the columns of the right matrix as well. With the $LU$ scheme, permuting whole columns will do the trick.

---

When you swap the rows only, you call it partial pivoting. When working with both, total pivoting.