The Lemmas of Linear Combination: Topics in Linear Algebra

Introduction To The Lemmas of Linear Combination

The present endeavor of this series on linear algebra centers around the essential computations associated with linear systems. This common thread unifies all topics pertaining to this subject. Our first article began elaborating on the primary methodology of deriving the solution for a linear system, the Gaussian method. We then sought a comprehensive means for describing the solutions of a linear system, the subject of our second article. Finally, our most recent article explored an extrapolation of the Gaussian method, Gaussian Jordan reduction. As we continue to explicate the computations associated with linear systems, we here address the various lemmas governing linear combination. These lemmas of linear combination form the basis by which we are capable of executing these computations.

Lemma #1: The Linear Combination Lemma

The first lemma of linear combination contends:

\text{A linear combination of a linear combination} \newline \text{is itself a linear combination}

This lemma implies that if we apply some type of computation to a certain linear combination, then this modified linear combination is also a linear combination.

Firstly, suppose we have a set of linear combinations that take the form:

c_1,_1x_1+\cdot \cdot \cdot +c_1,_nx_n \newline \cdot \newline \cdot \newline c_m,_1x_1+\cdot \cdot \cdot+c_m,_nx_n

Now, suppose that we apply the scalar ‘d’ to the linear combinations of these systems. This manipulation yields:

d_1(c_1,_1x_1+\cdot \cdot \cdot +c_1,_nx_n) \newline \enspace\cdot \newline \enspace\cdot \newline d_m(c_m,_1x_1+\cdot \cdot \cdot+c_m,_nx_n)

Distributing the scalar ‘d’ to components of the linear combinations yields:

\enspace\enspace\enspace(d_1c_1,_1+\cdot \cdot \cdot +d_mc_m,_1)x_1 \newline \cdot \newline \cdot \newline \enspace\enspace\enspace(d_1c_1,_n+\cdot \cdot \cdot+d_mc_m,_n)x_n

Finally, the linear combination above is a linear combination on the basis of the x’s.

Corollary to the First Lemma

From the first lemma of linear combinations, we can bring this back to the level of the linear system. In a system constituted by a matrix, it the first matrix is reducible to a second matrix, then each row of the second matrix is a linear combination of its respective row from the first matrix.

This definition relies entirely upon the second lemma from the previous article, which contends that the phraseology ‘reduces to’ is a statement of equivalence. The present corollary suggests that two inter-reducible matrices are by some computation equivalent. Therefore, there exists a finite number of computations that may be applied to matrix A to yield matrix B.

If matrix A may be converted to matrix B in zero steps, then the two matrices are equal. However, if the number of steps is greater than zero, then if the matrix B can be achieved in this number or less than this number of steps, then the rows of B must be linear combinations of A.

Lemma #2: In Echelon Form, a Nonzero Row is not a Linear Combination of Other Nonzero Rows

Lemma #2 implies that for a row of a matrix in echelon form, it is a linear combination of no other rows in the matrix. Let’s suppose that A constitutes a matrix in echelon form and has a number of non-zero rows. In theory, suppose that we desire to create a linear combination of all the non-zero rows together. If ‘pi‘ represents the ith row of the matrix, then we may model this comprehensive linear combination as:


Lemma #3: Every Matrix is Row Equivalent to a Reduced Row Echelon Matrix

For a matrix which, by Gaussian-Jordan reduction, has reached a state of reduced row echelon form, the progenitor matrix is row equivalent to the reduced matrix.

Suppose that we have a matrix with ‘n’ columns in the matrix, and suppose that ‘n’ is greater than 1. Also assume this matrix has ‘m’ rows. We may say that this matrix is an ‘m’ x ‘n’ matrix. Let’s call this matrix A, and populate this environment with matrices B and C which are both reduced echelon forms derived from A. Finally, Lemma #3 contends that the reduced echelon matrices B and C must be equal to each other.

Recall from Lemma #1 that there are a finite number of row operations for converting a matrix to its reduced form. Thus, there are a finite number of operations that bring matrix A to matrix B or C.

Suppose the matrix A has the following form:

a_1,_1x_1+a_1,_2x_2+\cdot\cdot\cdot+a_1,_nx_n=0\newline a_2,_1x_1+a_2,_2x_2+\cdot\cdot\cdot+a_2,_nx_n=0\newline \enspace\enspace\enspace\enspace\cdot\newline \enspace\enspace\enspace\enspace\cdot\newline a_m,_1x_1+a_m,_2x_2+\cdot\cdot\cdot+a_m,_nx_n=0

We know from our previous discussion of Gaussian Jordan reduction that if two matrices are inter-reducible, then the solutions for these matrices are the same. This is because the concept that a matrix ‘reduces to’ another matrix indicates their equivalence. Thus, the matrix B must have the same solution as matrix A such that:

b_1,_1x_1+b_1,_2x_2+\cdot\cdot\cdot+b_1,_nx_n=0\newline b_2,_1x_1+b_2,_2x_2+\cdot\cdot\cdot+b_2,_nx_n=0\newline \enspace\enspace\enspace\enspace\cdot\newline \enspace\enspace\enspace\enspace\cdot\newline b_m,_1x_1+b_m,_2x_2+\cdot\cdot\cdot+b_m,_nx_n=0

Furthermore, the matrix C must also have the same solution as matrix A and takes the form:

c_1,_1x_1+c_1,_2x_2+\cdot\cdot\cdot+c_1,_nx_n=0\newline c_2,_1x_1+c_2,_2x_2+\cdot\cdot\cdot+c_2,_nx_n=0\newline \enspace\enspace\enspace\enspace\cdot\newline \enspace\enspace\enspace\enspace\cdot\newline c_m,_1x_1+c_m,_2x_2+\cdot\cdot\cdot+c_m,_nx_n=0

Thus, suppose we subtract row ‘i’ of the C system from row ‘i’ of the B system. Next, this circumstance yields the formula:


Because we assume that the matrices are equivalent but not equal:

b_i,_n \not= c_i,_n

For that reason, xn=0. As a result, we know that B=C

Corollary to Lemma #3

Lemma #3 contends that if two different reduced row echelon matrices are derived from the same matrix, then they must be equal. The corollary to this lemma contends that if two reduced row echelon matrices are equal and derived from the same progenitor matrix, then the leading variables of those two derived matrices are the same.

Tie it All Together

When commencing with the Gaussian method, the initial motive is deriving a cohort of other matrices. We have noted that two matrices may be thought of as being related to each other if one may derived from the other, such that these are inter-reducible. If this is true, then this inter-reducibility is a phenomenon known as row equivalence. This row-equivalence divides sets of matrices into row-equivalent classes. While we discuss this topic with respect to row equivalence, we have made evident that the set of all matrices derived from the progenitor belong to row equivalent classes. This facilitates our comprehension of the fact that the reduced row echelon forms are unique but remain related.


The present article expands rather extensively on linear combinations and the lemmas of linear combinations which associate related systems together. The first lemma contends that if one linear combination is derived from another linear combination, both of these are themselves linear combinations. The corollary to this matter contends that if linear combinations are inter-reducible, then the matrices are row equivalent.

The second lemma of linear combination was relatively simple in that for a linear system in row echelon form, no row thereof is inter-reducible. This lemma itself gave rise to the third lemma, contending that two linear systems derived from the same progenitor, though unique, are row equivalent to each other as well as the progenitor. Together, these lemmas create an environment wherein we may relate matrices and linear systems together despite harboring moderately different structures.

If after all of this you find yourself confused on the lemmas of linear combination, consider checking out this resource for further insight. Nevertheless, reference the list below to visit other subjects concerning the computations of various linear systems.

  1. Gaussian Method of Solving Linear Systems
  2. Describing Solutions of Linear Systems
  3. Guide to Gaussian-Jordan Reduction

Leave a Reply

%d bloggers like this: