Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is it possible to use row and column operations "at the same time" on a matrix $A$? So, for example, first subtracting $row_1$ from $row_2$, and then choosing to multiply $column_3$ by a constant $c$? Or do you have to "stick to one method" when reducing a matrix? If so, can somebody explain why?

Edit: so let me put this more clearly. Suppose you have $$\left( \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right)$$

First I multiply row 2 by $\frac{a_{11}}{a_{21}}$, row 3 by $\frac{a_{11}}{a_{31}}$, then subtract row 1 from row 2 and row 3 so you end up with a matrix of a new general form: $$\left( \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ 0 & b_{22} & b_{23} \\ 0 & b_{32} & b_{33} \end{array} \right)$$

with $b_{ij}$ the new coefficients which were attained by our row operations. My question is: could you then say, subtract column 1 from columns 2 and 3 in order to get:

$$\left( \begin{array}{ccc} a_{11} & 0 & 0 \\ 0 & b_{22} & b_{23} \\ 0 & b_{32} & b_{33} \end{array} \right)?$$

Edit2: How come that, according to the answers, this is incorrect, even though this is the exact same thing Serge Lang does in his book "Introduction to Linear Algebra"? What's happening here? Are you telling me Serge Lang doesn't know how to reduce a matrix? Reminder: this is NOT a linear system we're solving for, and this is NOT an augmented matrix. It's just a matrix $A$.

Edit3: here is some more context.

share|improve this question
    
When we do row reduction without an augmented matrix, we wind up with a $U$ such that $Ax=0 \Leftrightarrow Ux=0$. When we do column operations, the $U$ we get at the end does not have this property. For example, $\begin{bmatrix} 1 & 1 \\ 1 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ -1 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \end{bmatrix}$ but $\begin{bmatrix} 1 & 0 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} 1 \\ -1 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \end{bmatrix}$ –  Ian Jul 10 at 20:17
    
Certainly you cannot do all those things if you have any division by $0$ going on. –  Adam Hughes Jul 10 at 20:20
4  
It depends on WHY you're wanting to reduce it. If you're trying to determine if a matrix is invertible -- then yes (that is you're checking to see if the matrix is similar to the identity matrix). You can use either one or both together. In general, though, row and column reduction are 2 different things. –  Bye_World Jul 10 at 20:32
6  
Dr. Lang makes it clear here the reason why row and column operations work in this case. It's because he doesn't care if he loses information about the linear transformation under consideration -- he only wants to find the rank of the matrix. Because the column rank and row rank are equivalent, you can use col or row or both operations to reduce the matrix. Again, you lose information about the transformation (always try to remember that matrices are just representations of linear transformations) -- but no information is lost about the rank. –  Bye_World Jul 10 at 20:51
3  
This is often done. For example the calculation of Smith normal form of a matrix requires both row and column operations. It all depends on the context of what you are doing. If you are calculating the determinant, you can do either. If you are solving a linear system, you cannot. A blanket answer is impossible. The following is the best I can say: A row operation amounts to a change of basis in the range - a column operation amounts to a change of basis in the domain. It depends on the task which (may be both, may be neither) is ok. –  Jyrki Lahtonen Jul 10 at 20:54

4 Answers 4

up vote 3 down vote accepted

What "reducing a matrix" means

One issue here is what is meant by "reducing a matrix". The only purpose I can see for reducing a matrix is to decide if the matrix has some specific property. Whatever property you are interested in has to remain unchanged under the operations you do or you have not succeeded in your purpose.

If you investigage Serge Lang's book closely, you will find that he had a specific purpose for reducing the matrix,(to find the rank, discussed below) which allows him to use column operations to acheive his aim.

It is important to note that for most people, the phrase "reducing a matrix" refers specifically to finding the Reduced Row Echelon Form (also known as RREF). As the name implies, RREF is defined using the rows of the matrix: 1. The leftmost nonzero entry in any row is a 1 (called a "leading 1"). 2. Leading 1's on lower rows are further to the right than leading 1's on higher rows. 3. Other entries in a column with a leading 1 are zero. 4. All rows consisting entirely of zeros are at the bottom of the matrix. Since you are defining this matrix in terms of rows, you must do row operations to acheive it. In fact, if you do use row operations, then given a particular starting matrix (which may or may not be square, by the way), there is precisely one RREF that it will reduce to. If you do column operations you will not arrive at this same matrix.

Relationships to solutions of equations

The point others have made about finding solutions is valid. Every matrix can be used to represent the coefficients of a system of linear equations, regardless of whether you want it to or not. Many of the important properties of matrices are strongly related to this system of linear equations, and so it is a good idea to have methods that preserve these properties.

For example, the set of solutions to $A\mathbf{x} = \mathbf{0}$ is the same as the set of solutions to the (homogeneous) linear equations, and the nonzero rows of the RREF form a basis for the space perpendicular to this space of solutions. Neither of these properties are preserved by column operations, but they are preserved by row operations.

Most importantly, just to reiterate: the solution to your homogeneous linear equations is definitely not preserved by column operations, and this is an important consideration regardless of whether you want your matrix to represent linear equations or not.

Note that there are things that column operations do preserve, such as the range of the linear transformation defined by your matrix. However a mixture of row and column operations will not preserve this, nor most of the properties you care about.

The inverse of a square matrix

One property that a mixture of row and column operations does preserve is invertibility. You can see this from the idea of elementary matrices.

Doing elementary row operations corresponds to multiplying on the left by an elementary matrix. For example, the row operation of "new R2 = R2 - 3R1" is produced on a 3 by n matrix when you multiply on the left by $\begin{pmatrix} 1 & 0 & 0 \\ -3 & 1 & 0\\ 0 & 0 & 1 \end{pmatrix}$. Column operations, on the other hand, are produced when you multiply by a matrix on the right hand side. The column operation of "new C2 = C2 - 3C1" is produced on an m by 3 matrix when you multiply on the right by $\begin{pmatrix} 1 & -3 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{pmatrix}$.

The process of finding the inverse of a square matrix by augmenting an identity and doing matching row operations on both works because of these elementary matrices. If you perform row operations on $A$ to get $I$ and the elementary matrices corresponding to these operations are $E_1$, ..., $E_k$, then we have $E_k ... E_1 A = I$ and so the inverse of $A$ must be $E_k ... E_1$. But this is equal to $E_k ... E_1 I$, which is what you get when you do all those row operations on the identity!

This would work perfectly well if you did column operations, however a mixture of the two is a bit harder to understand. Suppose you did row operations with matrices $E_1$, ..., $E_k$ and column operations with matrices $F_1$, ..., $F_h$ and you produced the identity as a result. Then $$ \begin{align} E_k \dots E_1 A F_1 \dots F_h &= I\\ A &= (E_1)^{-1} \dots (E_k)^{-1} I (F_h)^{-1} \dots (F_1)^{-1}\\ A^{-1} &= F_1 \dots F_h I E_k \dots E_1 \end{align} $$

This is not the result of doing the matching column operations and row operations on $I$ because the matrices are on the wrong side!

So if you can row-and-or-column reduce a matrix to the identity, then this proves that the matrix is invertible, but it is tricky to tell what the inverse actually is unless you do only row or only column operations.

Finally note that row and column operations simultaneously will allow you to calclate the determinant of a square matrix easily, and so there is a certain advantage to doing this. In particular a row/column operation of the type "new Ri = Ri + k Rj" or "new Ci = Ci + k Cj" will not change the determinant, so if you restrict yourself to those operations, you can get your matrix into a form where it is clear what the determinant is more quickly than restricting yourself to just one. However, it is worth stressing that this relates to my original comment about the purpose you are trying to achieve -- this is only really an advantage in the situation where you are finding determinants.

The rank of a matrix

Finally, this row-and-or-column reduction also does preserve the rank of your matrix. If you do this kind of reduction on any matrix, what you are guaranteed to produce eventually if you try is a matrix with some 1's down its main diagonal (but not necessarily all the way down) and zeros everywhere else. Something like these: $$ \begin{pmatrix} 1 & 0 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 & 0\\ 0 & 0 & 1 & 0& 0\end{pmatrix} \quad \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0& 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{pmatrix} $$

The number of 1's on that diagonal is the rank of your matrix. That is, it is the dimension of the column space and row space, and the dimension of the range of the linear transformation defined by your matrix, and n minus the dimension of the solution space to your system of equations. So the two matrices above have rank 3 and 2 respectively.

However, there is nothing in the final reduced form that tells you what the actual solutions to the equations are or what the bases for the spaces are. These can all be changed in ways that are not easy to follow if you do both row and column operations. If you did just column operations, then the leading-1 columns would be a basis for the range of the linear transformation, but with both row and column operations, these columns are all standard basis vectors and won't necessarily be correct. If you did just row operations, then the non-leading-1 columns would appear as the first several coordinates of the vectors in a basis for the null space of the matrix, but with both row and column operations these columns are all zero.

Summary

  1. Most people mean Reduced Row Echelon Form when they say "reduced matrix", which is defined by doing only row operations.
  2. Row operations preserve many useful properties of matrices and tell you certain information about matrices.
  3. Column operations preserve some useful properties of matrices and tell you certain information about matrices.
  4. Mixtures of row and column operations preserve only a small number of properties. In particular, a mixture will preserve the rank and the invertibility of a matrix (but will not provide bases for associated subspaces or the actual inverse itself).
share|improve this answer

Say you have a system of equations:

$$\begin{cases} a_{11} x_1+\ldots +a_{1m}x_m =b_1\\ \vdots \\ a_{n1}x_1+\ldots + a_{nm}x_m = b_n \end{cases}$$

Then the corresponding augmented matrix is

\begin{pmatrix} a_{11} & \ldots & a_{1m} & | & b_1 \\ \vdots & \ddots & \vdots & | & \vdots \\ a_{n1} & \ldots & a_{nm} & | & b_n\end{pmatrix}

Row operations correspond to adding and scaling equations or reordering them, which--by the force of regular algebra--doesn't change the overall system. Column operations however, DO change the system, because if we scale say the last column with all the $b$s, we see that this changes what we're trying to solve for.

In particular: say your first set of equations is just:

$$\begin{cases} x + y = 1 \\ x-y = 0\end{cases}$$

then the matrix is

$$\begin{pmatrix} 1 & 1 & | & 1 \\ 1 & -1 & | & 0\end{pmatrix}$$

It's easy to see that the solution is $x=y=1/2$, however, if we can scale the columns as well, we get $x=y=1$ just by scaling the last column by a factor of $2$, and if we could add columns, we would get the matrix:

$$\begin{pmatrix} 1 & 2 & | & 1 \\ 1 & -1 & | & 0\end{pmatrix}$$

by adding the last column to the second one. This gives us the system:

$$\begin{cases} x + 2y = 1 \\ x-y=0\end{cases}$$

where we see that $x=y=1/3$, a different solution.

share|improve this answer
    
Yes, I see, but I wasn't talking about finding a solution to a system of linear equations, or an augmented matrix. Just suppose you have a real-numbered matrix $A$; wouldn't it be possible to use column and row operations interchangeably? As long as it's just a "normal" matrix, without an added solution set, and I'd be interested in reducing it, wouldn't that be possible? –  Luke Jul 10 at 20:00
    
Here, I made an edit to clarify some things. If you could just take a look, I'd be very grateful! –  Luke Jul 10 at 20:14
    
Yes, assume that there's no division by zero going on. Is the presented method in my edit correct? –  Luke Jul 10 at 20:21

When you perform column operations rather than row operations, you change the solution rather than the right hand side. For brevity, let's say we are solving $Ax=b$; denote the new solution after a certain column operation by $x'$.

  • If you multiply column 1 by 2, $x'_1 = x_1/2$.
  • If you interchange columns 1 and 2, $x'_1=x_2$, $x'_2=x_1$.
  • If you add column 1 to column 2, $x'_1 = x_1 - x_2$. (Check this, I only tried this on a $2 \times 2$ example.)

These problems aside, yes, you can use both column operations and row operations in a Gaussian elimination procedure. There is fairly little practical use for doing so, however. About the only use is performing pivoting using both row and column exchanges (so-called "total pivoting", rather than "partial pivoting"), but one finds that in practice row exchanges alone are sufficient.

By the way, total pivoting is quite slow, because it requires scanning the entire matrix, rather than just one column, when finding each pivot. This increases the running time by a constant factor, whereas partial pivoting adds only quadratic time to a cubic procedure.

share|improve this answer
    
Thank you, that's a great answer, but I'd ask of you to read my reply to the other comment. I'm not interested in row-reducing an augmented matrix, I was interested in just reducing an arbitrary matrix $A$ without a specific solution set added to it. –  Luke Jul 10 at 20:02
    
But how come that Serge Lang, in his "Introduction to Linear Algebra", does exactly what I did in the edit? –  Luke Jul 10 at 20:19

Suppose we want to perform row and column operations on the matrix $A$. Performing a row operation is the same as multiplying on the left by a certain elementary matrix $E_R$; performing a column operation is the same as multiplying on the right by a certain elementary matrix $E_C$. Since $(E_R A)E_C = E_R(A E_C)$ (i.e., since matrix multiplication is associative), the order in which you perform a row operation and a column operation does not matter: you end up with the same matrix in either case.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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