The Big Theorem on Equivalencies

Let A be an m x n matrix [so that A has m rows and n columns] and let T: Rⁿ ---> R^m be the corresponding linear transformation.  That is, T is the function given by T(x) = Ax, for every x in Rⁿ.  [We also say that the function T is given by:  x ----> Ax.]

Furthermore, consider the transpose of A, denoted by A^T, and let S: R^m ---> Rⁿ be the linear transformation given by S(y) = A^T(y) for every y in R^m.

Below are listed three groups of statements: Group I, Group II and Group III.

Theorem: :
   (1) The statements in Group I are equivalent to each other.
   (2) The statements in Group II are equivalent to each other
   (3) The statements in Group III are equivalent to each other
furthermore:
   (4) When m = n, then all the statements in all the groups are
         all equivalent to each other.

GROUP I -- [The "one-to-one" group.] [And see HERE.]

(a) The linear transformation  T: Rⁿ ---> R^m is one-to-one.
     That is, if T(x₁) = T(x₂), then x₁ = x₂.
     That is, if Ax₁ = Ax₂, then x₁ = x_2.

(b) The linear system Ax = 0 has only the trivial solution. 
     That is, if Ax =  0, then x = 0.

(c) The matrix A has a pivot in each column.

(d) The n columns of the matrix A are independent vectors in R^m.

(e) There exists an n x m matrix C such that CA = I_n.

(f) The matrix A^T, the transpose of A, satisfies all the conditions of Group II.

GROUP II -- [The "onto" group.]

(a) The linear transformation  T: Rⁿ ---> R^m is onto.
     That is, for any vector b in R^m, there exists at least
     one vector, x, in Rⁿ such that T(x) = b.

(b) For any vector b in R^m, the linear system Ax = b always
      has at least one solution.

(b') For any vector b in R^m, the vector equation x₁a₁+ ... + x_na_n = b
      always has at least one solution.

(c) The matrix A has a pivot in each row.

(d) The n columns of the matrix A span R^m.

(e) There exists an m x n matrix D such that AD = I_m.

(f) The matrix A^T, the transpose of A, satisfies all the conditions of Group I.

GROUP III -- [The "invertible" group.]  [Assume: A is a square n x n matrix.]

(a) The matrix A is invertible.  That is, there exists an n x n matrix Z
      such that AZ = ZA = I_n.

(b) A is row equivalent to I_n.

(c) A has n pivots (one in each row) (equivalently, one in each column).

(d) There exits elementary matrices, E₁, E₂, ...., E_s
      such that E₁E₂...E_sA = I_n

(e) det (A) is not zero.

(f) The matrix A^T, the transpose of A, is invertible.

Remarks:

(1) If A satisfies any (hence all) of the conditions of Group I, then n < m.
(2) If A satisfies any (hence all) of the conditions of Group II, then n > m.

Some important reminders:

(1) If A is an m x n matrix with columns a₁, a₂, ...., a_n,
     that is, if A = [a₁  a₂  .... a_n], and if x is a column in Rⁿ with
     components x₁, x₂, ..., x_n, then the product Ax is given by the following
     linear combination of the columns of A:  x₁a₁ + a₂x₂ + .... + x_na_n.

(2) If A is an m x n matrix and B is an n x p matrix, then the product AB is
      the m x p matrix given by AB = [Ab₁ Ab₂ .... Ab_p],
      where b₁, b₂, ..., b_p are the p columns of B.

(3) A collection of vectors, v₁, v₂, ..., v_n, is said to be independent
     if the only linear combination of them that is zero is the trivial linear combination. 
     That is, if x₁v₁ + x₂v₂ +...+ x_nv_n = 0, then it must be that x₁ =  x₂ = .... = x_n = 0.

(4) [And thus..] A collection of vectors, v₁, v₂, ..., v_n, is said to be dependent
     there exists a non trivial linear combination of them that is zero.  That is, if there
     exists constants x₁, x₂, ..., x_n not all of which are zero (although some of them might be zero)
     such that  x₁v₁ + x₂v₂ +...+ x_nv_n = 0.

(5) There are actually a number of other equivalent conditions for independence.  We collect them below:  That is, the following conditions on vectors v₁, ..., v_p are equivalent:

(a) The vectors v₁, ..., v_p are independent (that is, if x₁v₁+...+x_pv_p = 0, then x₁ =...= x_n = 0.)

(b) If x₁v₁+...+x_pv_p = y₁v₁+...+y_pv_p, then x₁ = y₁, ..., x_p = y_p.

(c) For each i, v_i is not a linear combination of the remaining vectors.

(d) Span {v₁, ..., v_p} is not the Span of a proper subset of {v₁, ..., v_p}

(e) Span {v₁, ..., v_p}is not the Span of fewer than p vectors.

(f) Some p vectors in Span {v₁, ..., v_p}are independent.