Finding Set of Solutions From Rref

Determinants and Eigenvalues

Stephen Andrilli , David Hecker , in Elementary Linear Algebra (Fifth Edition), 2016

Determinant Criterion for Matrix Singularity

The next theorem gives an alternative way of determining whether the inverse of a given square matrix exists.

Theorem 3.5

An n × n matrix A is nonsingular if and only if $\left|\mathbf{A}\right|\ne 0.$

Proof

Let D be the unique matrix in reduced row echelon form for A. Now, using Theorem 3.3, we see that a single row operation of any type cannot convert a matrix having a nonzero determinant to a matrix having a zero determinant (why?). Because A is converted to D using a finite number of such row operations, Theorem 3.3 assures us that $\left|\mathbf{A}\right|$ and $\left|\mathbf{D}\right|$ are either both zero or both nonzero.

Now, if A is nonsingular (which implies D =I _n ), we know that $\left|\mathbf{D}\right|=1\ne 0$ and therefore $\left|\mathbf{A}\right|\ne 0,$ and we have completed half of the proof.

For the other half, assume that $\left|\mathbf{A}\right|\ne 0$ . Then $\left|\mathbf{D}\right|\ne 0$ . Because D is a square matrix with a staircase pattern of pivots, it is upper triangular. Because $\left|\mathbf{D}\right|\ne 0$ , Theorem 3.2 asserts that all main diagonal entries of D are nonzero. Hence, they are all pivots, and D =I _n . Therefore, row reduction transforms A to I _n , so A is nonsingular.

Notice that Theorem 3.5 agrees with Theorem 2.14 in asserting that an inverse for $\left[\begin{array}{ll}a& b\\ c& d\end{array}\right]$ exists if and only if $\left|\begin{array}{ll}a& b\\ c& d\end{array}\right|=ad-bc\ne 0.$

Theorems 2.15 and 3.5 together imply the following:

Corollary 3.6

Let A be an n × n matrix. Then rank(A) = n if and only if $\left|\mathbf{A}\right|\ne 0.$

Example 6

Consider the matrix $\mathbf{A}=\left[\begin{array}{ll}1& 6\\ -3& 5\end{array}\right].$ Now, $\left|\mathbf{A}\right|=23\ne 0.$ Hence, rank(A) = 2 by Corollary 3.6. Also, because A is the coefficient matrix of the system

$\left\{\begin{array}{rrrrr}x& +& 6y& =& 20\\ -3x& +& 5y& =& 9\end{array}\right.$

and $\left|\mathbf{A}\right|\ne 0,$ this system has a unique solution by Theorem 2.16. In fact, the solution is (2,3).

On the other hand, for the matrix

$\mathbf{B}=\left[\begin{array}{lll}1& 5& 1\\ 2& 1& -7\\ -1& 2& 6\end{array}\right],$

we have |B|=0. Thus, rank(B) < 3. Also, because B is the coefficient matrix for the homogeneous system

$\left\{\begin{array}{lllllll}\hfill x_1& +& 5x_2& +& x_3& =& 0\\ 2x_1& +& x_2& -& 7x_3& =& 0\\ \hfill -x_1& +& 2x_2& +& 6x_3& =& 0\end{array}\right.,$

this system has nontrivial solutions by Theorem 2.2. You can verify that its complete solution set is $\left\{\left.c(4,-1,1)\right|c\in \mathbb{R}\right\}.$

For reference, we summarize many of the results obtained in Chapters 2 and 3 in Table 3.1. You should be able to justify each equivalence in Table 3.1 by citing a relevant definition or result.

Table 3.1. Equivalent conditions for singular and nonsingular matrices

For an n×n matrix A, the following are all equivalent:	For an n×n matrix A, the following are all equivalent:
A is singular (A −1 does not exist).	A is nonsingular (A −1 exists).
Rank(A)≠n.	Rank(A) = n.
$\left|\mathbf{A}\right|=0.$	$\left|\mathbf{A}\right|\ne 0.$
A is not row equivalent to I n .	A is row equivalent to I n .
AX = 0 has a nontrivial solution for X.	AX = 0 has only the trivial solution for X.
AX = B does not have a unique solution (no solutions or infinitely many solutions).	AX = B has a unique solution for X (namely, X =A −1 B).

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128008539000037

Determinants and Eigenvalues

Stephen Andrilli , David Hecker , in Elementary Linear Algebra (Fourth Edition), 2010

Determinant Criterion for Matrix Singularity

The next theorem gives an alternative way of determining whether the inverse of a given square matrix exists.

Theorem 3.5

An n × n matrix A is nonsingular if and only if |A| ≠ 0.

Proof

Let D be the unique matrix in reduced row echelon form for A. Now, using Theorem 3.3, we see that a single row operation of type (I), (II), or (III) cannot convert a matrix having a nonzero determinant to a matrix having a zero determinant (why?). Because A is converted to D using a finite number of such row operations, Theorem 3.3 assures us that |A| and |D| are either both zero or both nonzero.

Now, if A is nonsingular (which implies D = I _n ), we know that |D| = 1 ≠ 0 and therefore |A| ≠ 0, and we have completed half of the proof.

For the other half, assume that |A| ≠ 0. Then |D| ≠ 0. Because D is a square matrix with a staircase pattern of pivots, it is upper triangular. Because |D| ≠ 0, Theorem 3.2 asserts that all main diagonal entries of D are nonzero. Hence, they are all pivots, and D = I _n . Therefore, row reduction transforms A to I _n , so A is nonsingular.

Notice that Theorem 3.5 agrees with Theorem 2.13 in asserting that an inverse for $\left[\begin{array}{cc}a& b\\ c& d\end{array}\right]$ exists if and only if $\left|\begin{array}{cc}a& b\\ c& d\end{array}\right|=ad-bc\ne 0$ .

Theorem 2.14 and Theorem 3.5 together imply the following:

Corollary 3.6

Let A be an n × n matrix. Then rankA = n if and only if |A| ≠ 0.

Example 6

Consider the matrix $A=\left[\begin{array}{cc}1& 6\\ -3& 5\end{array}\right]$ . Now, |A| = 23 ≠ 0. Hence, rank(A) = 2 by Corollary 3.6. Also, because A is the coefficient matrix of the system

$\{\begin{array}{rrrrr}\hfill x& \hfill +& \hfill 6y& \hfill =& \hfill 20\\ \hfill -3x& \hfill +& \hfill 5y& \hfill =& \hfill 9\end{array}$

and |A| ≠ 0, this system has a unique solution by Theorems 3.5 and 2.15. In fact, the solution is (2, 3).

On the other hand, the matrix

$B=\left[\begin{array}{ccc}1& 5& 1\\ 2& 1& -7\\ -1& 2& 6\end{array}\right]$

has determinant zero. Thus, rank(B) < 3. Also, because B is the coefficient matrix for the homogeneous system

$\{\begin{array}{ccccccc}{x}_1& +& 5x_2& +& x_3& =& 0\\ 2x_1& +& x_2& -& 7x_3& =& 0\\ -x_1& +& 2x_2& +& 6x_3& =& 0\end{array},$

this system has nontrivial solutions by Theorem 2.5. You can verify that its solution set is $\left\{c(4,-1,1)|c\in ℝ\right\}.$

For reference, we summarize many of the results obtained in Chapters 2 and 3 in Table 3.1. You should be able to justify each equivalence in Table 3.1 by citing a relevant definition or result.

Table 3.1. Equivalent conditions for singular and nonsingular matrices

Assume that A is an n × n matrix. Then the following are all equivalent:	Assume that A is an n × n matrix. Then the following are all equivalent:
A is singular (A −1 does not exist).	A is nonsingular (A −1 exists).
Rank(A) ≠ n.	Rank(A) = n.
|A = 0|.	|A ≠ 0|.
A is not row equivalent to I n .	A is row equivalent to I n .
AX = O has a nontrivial solution for X.	AX = O has only the trivial solution for X.
AX = B does not have a unique solution (no solutions or infinitely many solutions).	AX = B has a unique solution for X (namely, X = A −1 B).

Highlights

■

The determinant of an upper (or lower) triangular matrix is the product of the main diagonal entries.

■

A row operation of type (I) involving multiplication by c multiplies the determinant by c.

■

A row operation of type (II) has no effect on the determinant.

■

A row operation of type (III) negates the determinant.

■

If an n × n matrix A is multiplied by c to produce B, then |B| = cⁿ |A|.

■

The determinant of a matrix can be found by row reducing the matrix to upper triangular form and keeping track of the row operations performed and their effects on the determinant.

■

An n × n matrix A is nonsingular iff |A| ≠ 0 iff rank(A) = n.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123747518000226

Systems of Linear Equations

Stephen Andrilli , David Hecker , in Elementary Linear Algebra (Fourth Edition), 2010

Homogeneous Systems

Definition

A system of linear equations having matrix form AX = O, where O represents a zero column matrix, is called a homogeneous system.

For example, the following are homogeneous systems:

$\{\begin{array}{ccccc}2x& -& 3y& =& 0\\ -4x& +& 6y& =& 0\end{array}\text{and}\{\begin{array}{ccccccc}{\text{5x}}_{\text{1}}& -& {\text{2x}}_{\text{2}}& \text{+}& {\text{3x}}_{\text{3}}& \text{=}& \text{0}\\ {\text{6x}}_{\text{1}}& \text{+}& {\text{x}}_{\text{2}}& -& {\text{7x}}_{\text{3}}& \text{=}& \text{0}\\ -{\text{x}}_{\text{1}}& \text{+}& {\text{3x}}_{\text{2}}& \text{+}& {\text{x}}_{\text{3}}& \text{=}& \text{0}\end{array}.$

Notice that homogeneous systems are always consistent. This is because all of the variables can be set equal to zero to satisfy all of the equations. This special solution, (0,0,…,0), is called the trivial solution. Any other solution of a homogeneous system is called a nontrivial solution. For example, (0,0) is the trivial solution to the first homogeneous system shown, but (9,6) is a nontrivial solution. Whenever a homogeneous system has a nontrivial solution, it actually has infinitely many solutions (why?).

An important result about homogeneous systems is the following:

If the reduced row echelon form augmented matrix for a homogeneous system in n variables has fewer than n nonzero pivot entries, then the system has a nontrivial solution.

Example 3

Consider the following 3 × 3 homogeneous systems:

$\{\begin{array}{ccccccc}2x_1& +& x_2& +& 4x_3& =& 0\\ 3x_1& +& 2x_2& +& 5x_3& =& 0\\ & & -x_2& +& x_3& =& 0\end{array}\text{and}\{\begin{array}{ccccccc}4x_1& -& 8x_2& -& 2x_3& =& 0\\ 3x_1& -& 5x_2& -& 2x_3& =& 0\\ 2x_1& -& 8x_2& +& x_3& =& 0\end{array}.$

After Gauss-Jordan row reduction, the final augmented matrices for these systems are, respectively,

The first system has only the trivial solution because all three columns are pivot columns. However, the second system has a nontrivial solution because only two of its three variable columns are pivot columns (that is, there is at least one nonpivot column). The complete solution set for the second system is

$\left\{\left(\frac{3}{2}c,\text{undefined}\frac{1}{2}c,\text{undefined}c\right)|c\in ℝ\right\}=\left\{c\left(\frac{3}{2},\frac{1}{2},1\right)|c\in ℝ\right\}.$

Notice that if there are fewer equations than variables in a homogeneous system, we are bound to get at least one nonpivot column. Therefore, such a homogeneous system always has nontrivial solutions.

Example 4

Consider the following homogeneous system:

$\{\begin{array}{ccccccccccccc}{x}_1& -& 3x_2& +& 2x_3& -& 4x_4& +& 8x_5& +& 17x_6& =& 0\\ 3x_1& -& 9x_2& +& 6x_3& -& 12x_4& +& 24x_5& +& 49x_6& =& 0\\ -2x_1& +& 6x_2& -& 5x_3& +& 11x_4& -& 18x_5& -& 40x_6& =& 0\end{array}.$

Because this homogeneous system has fewer equations than variables, it has a nontrivial solution. To find all the solutions, we row reduce to obtain the final augmented matrix

$\left[\begin{array}{cccccc}①& -3& 0& 2& 4& 0\\ 0& 0& \text{undefined}①& -3& 2& 0\\ 0& 0& 0& 0& 0& \text{undefined}①\end{array}|\begin{array}{c}0\\ 0\\ 0\end{array}\right].$

The second, fourth, and fifth columns are nonpivot columns, so we can let x ₂, x ₄, and x ₅ take on any real values — say, b, d, and e, respectively. The values of the remaining variables are then determined by solving the equations x ₁ − 3b + 2d + 4e = 0, x ₃ − 3d + 2e = 0, and x ₆ = 0. The complete solution set is

$\left\{(3b-2d-4e,\text{undefined}b,\text{undefined}3d-2e,\text{undefined}d,\text{undefined}e,\text{undefined}0)|b,d,e\in ℝ\right\}.$

The solutions for the homogeneous system in Example 4 can be expressed as linear combinations of three particular solutions as follows:

$\begin{array}{l}(3b-2d-4e,b,3d-2e,d,e,0)\\ =b(3,1,0,0,0,0)+d(-2,0,3,1,0,0)+e(-4,0,-2,0,1,0).\end{array}$

Each particular solution was found by setting one independent variable equal to 1 and the others equal to 0. We will frequently find it useful to express solutions in this way.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123747518000184

Systems of Linear Equations

Stephen Andrilli , David Hecker , in Elementary Linear Algebra (Fifth Edition), 2016

Homogeneous Systems

Definition

A system of linear equations having matrix form AX  = 0, where 0 represents a zero column matrix, is called a homogeneous system.

For example, the following are homogeneous systems:

$\left\{\begin{array}{lllll}2x& -& 3y& =& 0\\ -4x& +& 6y& =& 0\end{array}\right.\text{and}\left\{\begin{array}{lllllll}5x_1& -& 2x_2& +& 3x_3& =& 0\\ 6x_1& +& x_2& -& 7x_3& =& 0\\ -x_1& +& 3x_2& +& x_3& =& 0\end{array}\right..$

Notice that homogeneous systems are always consistent. This is because all of the variables can be set equal to zero to satisfy all of the equations. This special solution, (0,0,…,0), is called the trivial solution. Any other solution of a homogeneous system is called a nontrivial solution. For example, for the first homogeneous system shown, (0,0) is the trivial solution, but (9,6) is a nontrivial solution. Whenever a homogeneous system has a nontrivial solution, it actually has infinitely many solutions (why?).

An important result about homogeneous systems is the following:

Theorem 2.2

Let AX  = 0 be a homogeneous system in n variables.

(1)

If the reduced row echelon form for A has fewer than n nonzero pivot entries then the system has a nontrivial solution (and hence an infinite number of solutions).

(2)

If the reduced row echelon form for A has exactly n nonzero pivot entries then the system has only the trivial solution.

Proof

Note that the augmented matrix for AX  = 0 is $\left[\left.\mathbf{A}\right|0\right]$ . When row reducing this augmented matrix, the column of zeroes beyond the augmentation bar never changes. Hence, the pivots will be the same whether we are row reducing A or row reducing $\left[\left.\mathbf{A}\right|0\right]$ . Now, if there are fewer than n nonzero pivots for A, then some variable of the system is an independent variable, and so there are infinitely many solutions. That is, there are nontrivial solutions in addition to the trivial solution, which proves part (1) of the theorem. If there is a nonzero pivot for every column of A, then there is a unique solution — that is, the trivial solution — which proves part (2) of the theorem.

Example 3

Consider the following 3 ×3 homogeneous systems:

$\left\{\begin{array}{lllllll}4x_1& -& 8x_2& -& 2x_3& =& 0\\ 3x_1& -& 5x_2& -& 2x_3& =& 0\\ 2x_1& -& 8x_2& +& x_3& =& 0\end{array}\right.\text{and}\left\{\begin{array}{lllll}2x_1+& x_2& +4x_3& =& 0\\ 3x_1& +2x_2& +5x_3& =& 0\\ & -x_2& +x_3& =& 0\end{array}\right..$

Applying Gauss-Jordan row reduction to the coefficient matrices for these systems, we obtain, respectively,

By part (1) of Theorem 2.2, the first system has a nontrivial solution because only 2 of the 3 columns of the coefficient matrix are pivot columns (that is, the coefficient matrix has at least one nonpivot column). Since the column of zeroes in the augmented matrix for this system is not affected by row reduction, the complete solution set for the first system is

$\left\{\left.\left(\frac{3}{2}c,\frac{1}{2}c,c\right)\right|c\in \mathbb{R}\right\}=\left\{c\left.\left(\frac{3}{2},\frac{1}{2},1\right)\right|c\in \mathbb{R}\right\}.$

On the other hand, by part (2) of Theorem 2.2, the second system has only the trivial solution because all 3 columns of the coefficient matrix are pivot columns.

Notice that if there are fewer equations than variables in a homogeneous system, we are bound to get at least one nonpivot column. Therefore, we have

Corollary 2.3

Let AX  = 0 be a homogeneous system of m linear equations in n variables. If m < n, then the system has a nontrivial solution.

Example 4

Consider the following homogeneous system:

$\left\{\begin{array}{lllllllllllll}{x}_1& -& 3x_2& +& 2x_3& -& 4x_4& +& 8x_5& +& 17x_6& =& 0\\ 3x_1& -& 9x_2& +& 6x_3& -& 12x_4& +& 24x_5& +& 49x_6& =& 0\\ -2x_1& +& 6x_2& -& 5x_3& +& 11x_4& -& 18x_5& -& 40x_6& =& 0\end{array}\right..$

Because this homogeneous system has fewer equations than variables, it has a nontrivial solution. To find all the solutions, we row reduce to obtain the final augmented matrix

$\left[\left.\begin{array}{llllll}& \mathrm{①}-3& 0& 2& 4& 0\\ 0& 0& -3& 2& 0\\ 0& 0& 0& 0& 0\end{array}\right|\begin{array}{l}0\\ 0\\ 0\end{array}\right].$

The 2nd, 4th, and 5th columns are nonpivot columns, so we can let x ₂,x ₄, and x ₅ take on any real values — say, b,d, and e, respectively. The values of the remaining variables are then determined by solving the equations x ₁ −3b  +   2d  +   4e  =   0,x ₃ −3d  +   2e  =   0, and x ₆  =   0. The complete solution set is

$\left\{\left.(3b-2d-4e,b,3d-2e,d,e,0)\right|b,d,e\in \mathbb{R}\right\}.$

Notice that the solutions for the homogeneous system in Example 4 can be expressed as linear combinations of three particular solutions as follows:

$\begin{array}{ll}\hfill & (3b-2d-4e,b,3d-2e,d,e,0)\hfill \\ \hfill & =b(3,1,0,0,0,0)+d(-2,0,3,1,0,0)+e(-4,0,-2,0,1,0).\hfill \end{array}$

Each particular solution was found by setting one independent variable equal to 1 and the others equal to 0. We will frequently find it useful to express solutions to homogeneous systems in this way.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128008539000025

Distances Between Bent Functions

Natalia Tokareva , in Bent Functions, 2015

11.2 Classification of Bent Functions at the Minimal Distance from the Quadratic Bent Function

It is well known that extended affine equivalence preserves Hamming distances between Boolean functions—that is,

$\mathrm{dist}(f,g)=\mathrm{dist}(A(f),A(g)),$

where A(⋅) is an arbitrary nondegenerate affine transformation of a Boolean function (i.e., a nondegenerate affine transformation of variables and adding an affine Boolean function; see Section 5.2).

According to Theorem 18, any quadratic bent function in n variables is equivalent to the function q(x) = x ₁ x _(n/2)+1 ⊕ x ₂ x _(n/2)+2 ⊕⋯ ⊕ x _n/2 x _n . It is convenient for us to deal with a quadratic bent function of this form. Thus, it is interesting to study bent functions at the minimal distance from only one bent function q.

To classify all bent functions at distance 2 ^n/2 from q let us introduce some notation. Let M be a binary k × n matrix in reduced row echelon form without zero rows. This means that

•

the leading number (the first nonzero number from the left) of a nonzero row is always strictly to the right of the leading coefficient of the row above it;

•

all entries in a column above a leading entry are zeroes;

•

there are exactly k leading numbers.

Such a matrix is called also a Gaussian-Jordan matrix (without zero rows). So, M looks like

$M=\left(\begin{array}{llllllll}1& *& 0& 0& *& 0& *& \dots \\ 0& 0& 1& 0& *& 0& *& \dots \\ 0& 0& 0& 1& *& 0& *& \dots \\ 0& 0& 0& 0& 0& 1& *& \dots \\ \dots & \dots & \dots & \dots \\ \end{array}\right).$

Note that for every linear subspace $L\subseteq {\mathbb{F}}_2^n$ of dimension k there is a unique matrix M in the reduced row echelon form with rows being basic vectors. Then the matrix is usually called the Gaussian-Jordan matrix of a subspace L.

Denote by ℓ(M) the subset of positions of leading numbers of rows in a matrix M. For instance, in our example given above, ℓ(M) = {1,3,4,6,…}.

In general, let the Gaussian-Jordan matrix have the form

Let us call a Gaussian-Jordan n/2 × n matrix Madmissible of order t if the following conditions hold:

•

A is a Gaussian-Jordan t × n/2 matrix.

•

C is a Gaussian-Jordan (n/2 − t) × n/2 matrix.

•

Linear subspaces of ${\mathbb{F}}_2^{n/2}$ with Gaussian-Jordan matrices A and C are orthogonal—that is, A ⋅ C ^T is the zero matrix.

•

All columns of B with numbers from ℓ(C) are zero.

•

A′ and B′ are matrices of size t × t obtained from A and B, respectively, after elimination of columns with numbers from ℓ(C). Then if t > 1,

$\left(\begin{array}{llllll}\hfill {a{}^{\prime }}^{(2)}\hfill & \hfill {a{}^{\prime }}^{(1)}\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill \dots \hfill & \hfill 0\hfill \\ \hfill \dots \hfill \\ \hfill {a{}^{\prime }}^{(t)}\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill \dots \hfill & \hfill 0\hfill & \hfill {a{}^{\prime }}^{(1)}\hfill \\ \hfill \dots \hfill \\ \hfill 0\hfill & \hfill {a{}^{\prime }}^{(3)}\hfill & \hfill {a{}^{\prime }}^{(2)}\hfill & \hfill 0\hfill & \hfill \dots \hfill & \hfill 0\hfill \\ \hfill \dots \hfill \\ \hfill 0\hfill & \hfill {a{}^{\prime }}^{(t)}\hfill & \hfill 0\hfill & \hfill \dots \hfill & \hfill 0\hfill & \hfill {a{}^{\prime }}^{(2)}\hfill \\ \hfill \dots \hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill \dots \hfill & \hfill {a{}^{\prime }}^{(t)}\hfill & \hfill {a{}^{\prime }}^{(t-1)}\hfill \\ \hfill \hfill \end{array}\right)\cdot \left(\begin{array}{l}\hfill {{b{}^{\prime }}^{(1)}}^{\mathrm{T}}\hfill \\ \hfill {{b{}^{\prime }}^{(2)}}^{\mathrm{T}}\hfill \\ \hfill \hfill \\ \hfill \hfill \\ \hfill \hfill \\ \hfill ⋮\hfill \\ \hfill \hfill \\ \hfill \hfill \\ \hfill \hfill \\ \hfill {{b{}^{\prime }}^{(t)}}^{\mathrm{T}}\hfill \\ \hfill \hfill \end{array}\right)=0,$

where a′ ⁽ⁱ⁾ and b′ ⁽ⁱ⁾ are the ith rows of A′ and B′, respectively.

Kolomeec proved [208] the following theorem (see also [210]):

Theorem 75

Let V be an affine subspace of ${\mathbb{F}}_2^n$ of dimension n/2. Then the bent function q(x) = x ₁ x _(n/2)+1 ⊕ x ₂ x _(n/2)+2 ⊕⋯ ⊕ x _n/2 x _n is affine on V if and only if V is a shift of a linear subspace with an admissible Gaussian-Jordan matrix.

For instance, if n = 4, the bent function x ₁ x ₂ ⊕ x ₃ x ₄ is affine on all linear subspaces (and all their shifts) with Gaussian-Jordan matrices

$\left(\begin{array}{llll}0& 0& 1& 0\\ 0& 0& 0& 1\\ \end{array}\right),\left(\begin{array}{llll}1& 0& *& 0\\ 0& 0& 0& 1\\ \end{array}\right),\left(\begin{array}{llll}1& 1& 0& *\\ 0& 0& 1& 1\\ \end{array}\right),$

$\left(\begin{array}{llll}0& 1& 0& *\\ 0& 0& 1& 0\\ \end{array}\right),\left(\begin{array}{llll}1& 0& *& 0\\ 0& 1& 0& *\\ \end{array}\right),\left(\begin{array}{llll}1& 0& *& 1\\ 0& 1& 1& *\\ \end{array}\right).$

Thus, by Theorems 74 and 75 in order to count the number of bent functions at a distance 2 ^n/2 from the quadratic bent function one has to enumerate all the affine subspaces of dimension n/2 with admissible Gaussian-Jordan matrices. This is done in [208], where the following theorem is proven:

Theorem 76

Any quadratic bent function in n variables has exactly $2^{n/2}{\prod }_{i=1}^{n/2}(2^i+1)$ bent functions at the minimal possible distance 2 ^n/2 from it.

For instance, there are 60 bent functions at the minimal possible distance 4 from a bent function in four variables (since every such bent function is quadratic).

The number from Theorem 76 can be estimated as

$2^{n(n+6)/8}<2^{n/2}\cdot (2^1+1)\cdot \cdots \cdot (2^{n/2}+1)<3\cdot 2^{n(n+6)/8}.$

Note that asymptotically

$2^{n/2}\cdot (2^1+1)\cdot \cdots \cdot (2^{n/2}+1)\approx 2.38\cdot 2^{n(n+6)/8}.$

It is interesting that more than one-third of admissible Gaussian-Jordan matrices (that we use in Theorem 75) can be constructed in a very simple manner. Namely, all matrices of the form $\left(\begin{array}{ll}E& T\\ \end{array}\right)$ , where E is the identity matrix of size n/2 × n/2 and matrix T is an arbitrary symmetric matrix of size n/2 × n/2, are admissible Gaussian-Jordan matrices.

Note also that every bent function at the minimal distance 2 ^n/2 from the quadratic bent function in n variables is equivalent to a McFarland bent function.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B978012802318100011X

R

Fred E. Szabo PhD , in The Linear Algebra Survival Guide, 2015

Reduced Row Echelon Matrix

The leading entry of a nonzero row of a matrix in row echelon form is called a pivot of the matrix. An m-by-n row echelon matrix is in reduced row echelon form if it has the following properties: Either the matrix is a zero matrix or all of its pivots are 1 and all entries above its pivots are 0.

The RowReduce function of Mathematica reduces a matrix to its reduced row echelon form.

Illustration

■

A 4-by-5 reduced row echelon matrix

$\left(\begin{array}{ccccc}\hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{1}\hfill & \hfill \mathtt{8}\hfill & \hfill \mathtt{1}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{5}\hfill & \hfill \mathtt{4}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{6}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill \end{array}\right)$

The matrix is a matrix in row echelon form, but is not in reduced row echelon form.

■

Reduction of a 4-by-5 matrix to reduced row echelon form

$\mathsf{A}=\left(\begin{array}{ccccc}\hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{1}\hfill & \hfill \mathsf{8}\hfill & \hfill \mathsf{1}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{5}\hfill & \hfill \mathsf{4}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{6}\hfill \\ \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill & \hfill \mathsf{0}\hfill \end{array}\right)$

{{0, 0, 1, 8, 1}, {0, 0, 0, 5, 4}, {0, 0, 0, 0, 6}, {0, 0, 0, 0, 0}}

MatrixForm [B   =   RowReduce [A]]

$\left(\begin{array}{ccccc}\hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{1}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{1}\hfill & \hfill \mathtt{0}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{1}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill \end{array}\right)$

■

Reduction of a random 3-by-3 real matrix to reduced row echelon form

$\mathsf{A}=\left(\begin{array}{ccc}\hfill \mathsf{2}.\mathsf{0716982088321423}‵\hfill & \hfill \mathsf{2}.\mathsf{497526720307203}‵\hfill & \hfill \mathsf{7}.\mathsf{236524211079711}‵\hfill \\ \hfill \mathsf{5}.\mathsf{554095004848561}‵\hfill & \hfill \mathsf{1}.\mathsf{9196532271480322}‵\hfill & \hfill \mathsf{0}.\mathsf{9904680439688676}‵\hfill \\ \hfill \mathsf{5}.\mathsf{341640232827222}‵\hfill & \hfill \mathsf{1}.\mathsf{875793841070399}‵\hfill & \hfill \mathsf{8}.\mathsf{202469374845403}‵\hfill \end{array}\right)\text{;}$

MatrixForm [B   =   RowReduce [A]]

$\left(\begin{array}{ccc}\hfill \mathtt{1}\hfill & \hfill \mathtt{0}\mathtt{.}\hfill & \hfill \mathtt{0}\mathtt{.}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{1}\hfill & \hfill \mathtt{0}\mathtt{.}\hfill \\ \hfill \mathtt{0}\hfill & \hfill \mathtt{0}\hfill & \hfill \mathtt{1}\hfill \end{array}\right)$

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780124095205500254

Linear Equations and Eigensystems

G.R. Lindfield , J.E.T. Penny , in Numerical Methods (Third Edition), 2012

2.2 Linear Equation Systems

In general, a linear equation system can be written in matrix form as

(2.5) $\text{Ax}=\text{b}$

where A is an n × n matrix of known coefficients, b is a column vector of n known coefficients, and x is the column vector of n unknowns. We have already seen an example of this type of equation system in Section 2.1 where the matrix equation (2.2) is the matrix equivalent of the linear equations (2.1).

The equation system (2.5) is called homogeneous if b = 0 and inhomogeneous if b ≠ 0. Before attempting to solve an equation system it is reasonable to ask if it has a solution and if so is it unique? A linear inhomogeneous equation system may be consistent and have one or an infinity of solutions or be inconsistent and have no solution. This is illustrated in Figure 2.2 for a system of three equations in three variables x ₁, x ₂, and x ₃. Each equation represents a plane surface in the x ₁, x ₂, x ₃ space. In Figure 2.2(a) the three planes have a common point of intersection. The coordinates of the point of intersection give the unique solution for the three equations. In Figure 2.2(b) the three planes intersect in a line. Any point on the line of intersection represents a solution so there is no unique solution but an infinite number of solutions satisfying the three equations. In Figure 2.2(c) two of the surfaces are parallel to each other and therefore they never intersect, while in Figure 2.2(d) the line of intersection of each pair of surfaces is different. In both of these cases there is no solution and the equations these surfaces represent are inconsistent.

Figure 2.2. Three intersecting planes representing three equations in three variables. (a) Three plane surfaces intersecting in a point. (b) Three plane surfaces intersecting in a line. (c) Three plane surfaces, two of which do not intersect. (d) Three plane surfaces intersecting in three lines.

To obtain an algebraic solution to the inhomogeneous equation system (2.5) we multiply both sides of (2.5) by a matrix called the inverse of A, denoted by A ⁻¹:

(2.6) ${\text{A}}^{-1}\text{Ax}={\text{A}}^{-1}\text{b}$

where A ⁻¹ is defined by

(2.7) $A^{-1}A=A{A}^{-1}=I$

and I is the identity matrix. Thus we obtain

(2.8) $\text{x}={\text{A}}^{-1}\text{b}$

The standard algebraic formula for the inverse of A is

(2.9) ${\text{A}}^{-1}=\text{adj}(\text{A})/|\text{A}|$

where |A| is the determinant of A and adj(A) is the adjoint of A. The determinant and the adjoint of a matrix are defined in Appendix A. Equations (2.8) and (2.9) are algebraic statements allowing us to determine x but they do not provide an efficient means of solving the system because computing A ⁻¹ using (2.9) is extremely inefficient, involving order $(n+1)!$ multiplications where n is the number of equations. However, (2.9) is theoretically important because it shows that if |A| = 0 then A does not have an inverse. The matrix A is then said to be singular and a unique solution for x does not exist. Thus establishing that |A| is nonzero is one way of showing that an inhomogeneous equation system is a consistent system with a unique solution. It is shown in Sections 2.6 and 2.7 that (2.5) can be solved without formally determining the inverse of A.

An important concept in linear algebra is the rank of a matrix. For a square matrix, the rank is the number of independent rows or columns in the matrix. Independence can be explained as follows. The rows (or columns) of a matrix can clearly be viewed as a set of vectors. A set of vectors is said to be linearly independent if none of them can be expressed as a linear combination of any of the others. By linear combination we mean a sum of scalar multiples of the vectors. For example, the matrix

$\left[\begin{array}{ccc}1& 2& 3\\ -2& 1& 4\\ -1& 3& 4\end{array}\right]\text{or}\left[\begin{array}{c}\left[\begin{array}{ccc}1& 2& 3\end{array}\right]\\ \left[\begin{array}{ccc}-2& 1& 4\end{array}\right]\\ \left[\begin{array}{ccc}-1& 3& 7\end{array}\right]\end{array}\right]\text{or}\left[\begin{array}{ccc}\left[\begin{array}{c}1\\ 2\\ 3\end{array}\right]& \left[\begin{array}{c}-2\\ 1\\ 4\end{array}\right]& \left[\begin{array}{c}-1\\ 3\\ 7\end{array}\right]\end{array}\right]$

has linearly dependent rows and columns. This is because $\text{row}3-\text{row}1-\text{row}2=0$ and $\text{column}3-2(\text{column}2)+\text{column}1=0$ . There is only one equation relating the rows (or columns) and thus there are two independent rows (or columns). Hence this matrix has a rank of 2. Now consider

$\left[\begin{array}{ccc}\hfill 1\hfill & \hfill 2\hfill & \hfill 3\hfill \\ \hfill 2\hfill & \hfill 4\hfill & \hfill 6\hfill \\ \hfill 3\hfill & \hfill 6\hfill & \hfill 9\hfill \end{array}\right]$

Here $\text{row}2=2(\text{row}1)$ and $\text{row}3=3(\text{row}1)$ . There are two equations relating the rows and hence only one row is independent and the matrix has a rank of 1. Note that the number of independent rows and columns in a square matrix is identical; that is, its row rank and column rank are equal. In general matrices may be nonsquare and the rank of an m × n matrix A is written rank(A). Matrix A is said to be of full rank if rank(A) = min(m, n); otherwise $\text{rank}(\text{A})<\text{min}(m,n)$ and A is said to be rank deficient. Matlab provides the function rank, which works with both square and nonsquare matrices. In practice, Matlab determines the rank of a matrix from its singular values; see Section 2.10.

For example, consider the following Matlab statements:

>> D = [1 2 3;3 4 7;4 -3 1;-2 5 3;1 -7 6]

D =

  1   2   3

  3   4   7

  4   -3   1

  -2   5   3

  1   -7   6

>> rank(D)

ans =

  3

Thus D is of full rank since the rank equals the minimum size of the matrix.

A useful operation in linear algebra is the conversion of a matrix to its reduced row echelon form (RREF). The RREF is defined in Appendix A. In Matlab we can use the rref function to compute the RREF of a matrix as follows:

>> rref(D)

ans =

  1   0   0

  0   1   0

  0   0   1

  0   0   0

  0   0   0

It is a property of the RREF of a matrix that the number of rows with at least one nonzero element equals the rank of the matrix. In this example we see that there are three rows in the RREF of the matrix containing a nonzero element, confirming that the matrix rank is 3. The RREF also allows us to determine whether a system has a unique solution or not.

We have discussed a number of important concepts relating to the nature of linear equations and their solutions. We now summarize the equivalencies between these concepts. Let A be an n × n matrix. If Ax = b is consistent and has a unique solution, then all of the following statements are true:

Ax = 0 has only the trivial solution x = 0.

A is nonsingular and $\det (\text{A})\ne 0$ .

The RREF of A is the identity matrix.

A has n linearly independent rows and columns.

A has full rank, i.e., rank(A) = n.

In contrast, if Ax = b is either inconsistent or consistent but with more than one solution, then all of the following statements are true:

Ax = 0 has more than one solution.

A is singular and $\det (\text{A})=0$ .

The RREF of A contains at least one zero row.

A has linearly dependent rows and columns.

A is rank deficient, i.e., $\text{rank}(\text{A})<n$ .

So far we have only considered the case where there are as many equations as unknowns. Now we consider the cases where there are fewer or more equations than unknown variables.

If there are fewer equations than unknowns, then the system is said to be underdetermined. The equation system does not have a unique solution; it is either consistent with an infinity of solutions, or inconsistent with no solution. These conditions are illustrated by Figure 2.3. The diagram shows two plane surfaces in three-dimensional space, representing two equations in three variables. It is seen that the planes either intersect in a line so that the equations are consistent with an infinity of solutions represented by the line of intersection, or the surfaces do not intersect and the equations they represent are inconsistent.

Figure 2.3. Planes representing an underdetermined system of equations. (a) Two plane surfaces intersecting in a line. (b) Two plane surfaces which do not intersect.

Consider the following system of equations:

$\left[\begin{array}{cccc}\hfill 1& \hfill 2& \hfill 3& \hfill 4\\ \hfill -4& \hfill 2& \hfill -3& \hfill 7\end{array}\right]\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \\ \hfill x_3\hfill \\ \hfill x_4\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 3\hfill \end{array}\right]$

This underdetermined system can be rearranged as follows:

$\left[\begin{array}{cc}\hfill 1& \hfill 2\\ \hfill -4& \hfill 2\end{array}\right]\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \end{array}\right]+\left[\begin{array}{cc}\hfill 3& \hfill 4\\ \hfill -3& \hfill 7\end{array}\right]\left[\begin{array}{c}\hfill x_3\hfill \\ \hfill x_4\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 3\hfill \end{array}\right]$

or

$\left[\begin{array}{cc}\hfill 1& \hfill 2\\ \hfill -4& \hfill 2\end{array}\right]\left[\begin{array}{c}\hfill x_1\hfill \\ \hfill x_2\hfill \end{array}\right]=\left[\begin{array}{c}\hfill 1\hfill \\ \hfill 3\hfill \end{array}\right]-\left[\begin{array}{cc}\hfill 3& \hfill 4\\ \hfill -3& \hfill 7\end{array}\right]\left[\begin{array}{c}\hfill x_3\hfill \\ \hfill x_4\hfill \end{array}\right]$

Thus we have reduced this to a system of two equations in two unknowns, provided values are assumed for x ₃ and x ₄. Thus the problem has an infinity of solutions, depending on the values chosen for x ₃ and x ₄.

If a system has more equations than unknowns, then the system is said to be overdetermined. Figure 2.4 shows four plane surfaces in three-dimensional space, representing four equations in three variables. Figure 2.4(a) shows all four planes intersecting in a single point so that the system of equations is consistent with a unique solution. Figure 2.4(b) shows all the planes intersecting in a line and this represents a consistent system with an infinity of solutions. Figure 2.4(d) shows planes that represent an inconsistent system of equations with no solution. In Figure 2.4(c) the planes do not intersect in a single point and so the system of equations is inconsistent. However, in this example the points of intersection of groups of three planes (i.e., (S1, S2, S3), (S1, S2, S4), (S1, S3, S4), and (S2, S3, S4)) are close to each other and a mean point of intersection could be determined and used as an approximate solution. This example of marginal inconsistency often arises because the coefficients in the equations are determined experimentally; if the coefficients were known exactly, it is likely that the equations would be consistent with a unique solution. Rather than accepting that the system is inconsistent we may ask what the best solution is that satisfies the equations approximately. In Sections 2.11 and 2.12 we deal with the problem of overdetermined and underdetermined systems in more detail.

Figure 2.4. Planes representing an overdetermined system of equations. (a) Four plane surfaces intersecting in a point. (b) Four plane surfaces intersecting in a line. (c) Four plane surfaces not intersecting at a single point; points of intersection of (S1, S2, S3) and (S1, S2, S4) are visible. (d) Four plane surfaces representing inconsistent equations.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780123869425000023

Linear Transformations

Stephen Andrilli , David Hecker , in Elementary Linear Algebra (Fifth Edition), 2016

Finding the Range From the Matrix of a Linear Transformation

Next, we determine a method for finding a basis for the range of L: ${\mathbb{R}}^n\to {\mathbb{R}}^m$ given by L(X) = AX. In Section 1.5 we saw that AX can be expressed as a linear combination of the columns of A. In particular, if X = [x ₁,…,x _n ], then $\mathbf{AX}=x_1\left(\text{1st column of}\mathbf{A}\right)+\cdots +x_n\left(n\text{th column of}\mathbf{A}\right)$ . Thus, range(L) is spanned by the set of columns of A; that is, range(L) = span({columns of A}). Note that L(e _i ) equals the ith column of A. Thus, we can also say that {L(e ₁),…,L(e _n )} spans range(L).

The fact that the columns of A span range(L) combined with the Independence Test Method yields the following general technique for finding a basis for the range:

Method for Finding a Basis for the Range of a Linear Transformation (Range Method)

Let L: ${\mathbb{R}}^n\to {\mathbb{R}}^m$ be a linear transformation given by L(X) = A X, for some m × n matrix A. To find a basis for range(L), perform the following steps:

Step 1:

Find B , the reduced row echelon form of A.

Step 2:

Form the set of those columns of A whose corresponding columns in B have nonzero pivots. This set is a basis for range(L).

Example 5

Consider the linear transformation L: ${\mathbb{R}}^5\to {\mathbb{R}}^4$ given in Example 4. After row reducing the matrix A for L we obtained a matrix B in reduced row echelon form having nonzero pivots in columns 1, 3, and 5. Hence, columns 1, 3, and 5 of A form a basis for range(L). In particular, we get the basis {[8,4,−2,6], [16,10,−5,15],[0,−4,7,−7]}, and so $dim(\text{range}(L))=3$ .

From Examples 4 and 5, we see that $dim(ker(L))+dim(\text{range}(L))=2+3=5=dim({\mathbb{R}}^5)=dim(\text{domain}(L))$ , for the given linear transformation L. We can understand why this works by examining our methods for calculating bases for the kernel and range. For $ker(L)$ , we get one basis vector for each independent variable, which corresponds to a nonpivot column of A after row reducing. For range(L), we get one basis vector for each pivot column of A. Together, these account for the total number of columns of A, which is the dimension of the domain.

The fact that the number of nonzero pivots of A equals the number of nonzero rows in the reduced row echelon form matrix for A shows that $dim(\text{range}(L))=\text{rank}\left(\mathbf{A}\right)$ . This result is stated in the following theorem, which also holds when bases other than the standard bases are used (see Exercise 17).

Theorem 5.9

If $L:{\mathbb{R}}^n\to {\mathbb{R}}^m$ is a linear transformation with matrix A with respect to any bases for ${\mathbb{R}}^n$ and ${\mathbb{R}}^m$ , then

(1)

$dim(\text{range}(L))=\text{rank}\left(\mathbf{A}\right)$

(2)

$dim(ker(L))=n-\text{rank}\left(\mathbf{A}\right)$

(3)

$dim\left(ker(L)\right)+dim\left(\text{range}(L)\right)=dim\left(\text{domain}(L)\right)=n$ .

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128008539000050

Matrices and vectors: topics from linear algebra and vector calculus

Martha L. Abell , James P. Braselton , in Mathematica by Example (Sixth Edition), 2022

5.3.1 Fundamental subspaces associated with matrices

Let $\mathbf{A}=\left(a_{ij}\right)$ be an $n\times m$ matrix with entry $a_{ij}$ in the ith row and jth column. The row space of A, $\mathrm{row}(\mathbf{A})$ , is the spanning set of the rows of A; the column space of A, $\mathrm{col}(\mathbf{A})$ , is the spanning set of the columns of A. If A is any matrix, then the dimension of the column space of A is equal to the dimension of the row space of A. The dimension of the row space (column space) of a matrix A is called the rank of A. The nullspace of A is the set of solutions to the system of equations $\mathbf{Ax}=\mathbf{0}$ . The nullspace of A is a subspace, and its dimension is called the nullity of A. The rank of A is equal to the number of nonzero rows in the row echelon form of A; the nullity of A is equal to the number of zero rows in the row echelon form of A. Thus if A is a square matrix, the sum of the rank of A and the nullity of A is equal to the number of rows (columns) of A.

1.

NullSpace[A] returns a list of vectors, which form a basis for the nullspace (or kernel) of the matrix A.

2.

RowReduce[A] yields the reduced row echelon form of the matrix A.

Example 5.23

Place the matrix

$\mathbf{A}=\left(\begin{array}{ccccc}\hfill -1\hfill & \hfill -1\hfill & \hfill 2\hfill & \hfill 0\hfill & \hfill -1\hfill \\ \hfill -2\hfill & \hfill 2\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill -2\hfill \\ \hfill 2\hfill & \hfill -1\hfill & \hfill -1\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill -1\hfill & \hfill -1\hfill & \hfill 1\hfill & \hfill 2\hfill & \hfill 2\hfill \\ \hfill 1\hfill & \hfill -2\hfill & \hfill 2\hfill & \hfill -2\hfill & \hfill 0\hfill \end{array}\right)$

in reduced row echelon form. What is the rank of A? Find a basis for the nullspace of A.

Solution

We begin by defining the matrix matrixa. Then RowReduce is used to place matrixa in reduced row echelon form.

$\mathbf{\text{capa}}\mathbf{=}\mathbf{\{}\mathbf{\{}\mathbf{-}\mathbf{1}\mathbf{,}\mathbf{-}\mathbf{1}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{0}\mathbf{,}\mathbf{-}\mathbf{1}\mathbf{\}}\mathbf{,}\mathbf{\{}\mathbf{-}\mathbf{2}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{0}\mathbf{,}\mathbf{0}\mathbf{,}\mathbf{-}\mathbf{2}\mathbf{\}}\mathbf{,}$

$\mathbf{\{}\mathbf{2}\mathbf{,}\mathbf{-}\mathbf{1}\mathbf{,}\mathbf{-}\mathbf{1}\mathbf{,}\mathbf{0}\mathbf{,}\mathbf{1}\mathbf{\}}\mathbf{,}\mathbf{\{}\mathbf{-}\mathbf{1}\mathbf{,}\mathbf{-}\mathbf{1}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{2}\mathbf{\}}\mathbf{,}$

$\mathbf{\{}\mathbf{1}\mathbf{,}\mathbf{-}\mathbf{2}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{-}\mathbf{2}\mathbf{,}\mathbf{0}\mathbf{\}}\mathbf{\}}\mathbf{;}$

$\mathbf{\text{RowReduce}}\mathbf{[}\mathbf{\text{capa}}\mathbf{]}\mathbf{\text{//}}\mathbf{\text{MatrixForm}}$

$\left(\begin{array}{ccccc}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill -2\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill -2\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill -2\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right)$

Because the row-reduced form of matrixa contains four nonzero rows, the rank of A is 4, and thus the nullity is 1. We obtain a basis for the nullspace with NullSpace.

$\mathbf{\text{NullSpace}}\mathbf{[}\mathbf{\text{capa}}\mathbf{]}$

$\{\{2,2,2,1,0\}\}$

As expected, because the nullity is 1, a basis for the nullspace contains one vector.   □

Example 5.24

Find a basis for the column space of

$\mathbf{B}=\left(\begin{array}{ccccc}\hfill 1\hfill & \hfill -2\hfill & \hfill 2\hfill & \hfill 1\hfill & \hfill -2\hfill \\ \hfill 1\hfill & \hfill 1\hfill & \hfill 2\hfill & \hfill -2\hfill & \hfill -2\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 2\hfill & \hfill -1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill -2\hfill & \hfill 0\hfill \\ \hfill -2\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 2\hfill \end{array}\right).$

Solution

A basis for the column space of B is the same as a basis for the row space of the transpose of B. We begin by defining matrixb, and then using Transpose to compute the transpose of matrixb, naming the resulting output tb.

$\mathbf{\text{matrixb}}\mathbf{=}\mathbf{\{}\mathbf{\{}\mathbf{1}\mathbf{,}\mathbf{-}\mathbf{2}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{-}\mathbf{2}\mathbf{\}}\mathbf{,}\mathbf{\{}\mathbf{1}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{-}\mathbf{2}\mathbf{,}\mathbf{-}\mathbf{2}\mathbf{\}}\mathbf{,}$

$\mathbf{\{}\mathbf{1}\mathbf{,}\mathbf{0}\mathbf{,}\mathbf{0}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{-}\mathbf{1}\mathbf{\}}\mathbf{,}\mathbf{\{}\mathbf{0}\mathbf{,}\mathbf{0}\mathbf{,}\mathbf{0}\mathbf{,}\mathbf{-}\mathbf{2}\mathbf{,}\mathbf{0}\mathbf{\}}\mathbf{,}$

$\mathbf{\{}\mathbf{-}\mathbf{2}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{0}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{2}\mathbf{\}}\mathbf{\}}\mathbf{;}$

$\mathbf{\text{tb}}\mathbf{=}\mathbf{\text{Transpose}}\mathbf{[}\mathbf{\text{matrixb}}\mathbf{]}$

$\{\{1,1,1,0,-2\},\{-2,1,0,0,1\},\{2,2,0,0,0\},\{1,-2,2,-2,1\},\{-2,-2,-1,0,2\}\}$

Next, we use RowReduce to row reduce tb and name the result rrtb. A basis for the column space consists of the first four elements of rrtb. We also use Transpose to show that the first four elements of rrtb are the same as the first four columns of the transpose of rrtb. Thus the jth column of a matrix A can be extracted from A with Transpose [A][[j]].

$\mathbf{\text{rrtb}}\mathbf{=}\mathbf{\text{RowReduce}}\mathbf{[}\mathbf{\text{tb}}\mathbf{]}\mathbf{;}$

$\mathbf{\text{Transpose}}\mathbf{[}\mathbf{\text{rrtb}}\mathbf{]}\mathbf{\text{//}}\mathbf{\text{MatrixForm}}$

$\left(\begin{array}{ccccc}\hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill -\frac{1}{3}\hfill & \hfill \frac{1}{3}\hfill & \hfill -2\hfill & \hfill -3\hfill & \hfill 0\hfill \end{array}\right)$

We extract the first four elements of rrtb with Take. The results correspond to a basis for the column space of B.

$\mathbf{\text{Take}}\mathbf{[}\mathbf{\text{rrtb}}\mathbf{,}\mathbf{4}\mathbf{]}$

$\{\{1,0,0,0,-\frac{1}{3}\},\{0,1,0,0,\frac{1}{3}\},\{0,0,1,0,-2\},\{0,0,0,1,-3\}\}$   □

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128241639000100

Linear Equations and Eigensystems

George Lindfield , John Penny , in Numerical Methods (Fourth Edition), 2019

2.10 Singular Value Decomposition

The singular value decomposition (SVD) of an $m\times n$ matrix A is given by

(2.23) $\mathbf{A}={\mathbf{USV}}^{\mathsf{T}}(\text{or}\mathbf{A}={\mathbf{USV}}^{\mathsf{H}}\text{ if}\mathbf{A}\text{ is complex})$

where U is an orthogonal $m\times m$ matrix and V is an orthogonal $n\times n$ matrix. If A is complex then U and V are unitary matrices. In all cases S is a real diagonal $m\times n$ matrix. The elements of the leading diagonal of this matrix are called the singular values of A. Normally they are arranged in decreasing value so that $s_1>s_2>...>s_n$ . Thus,

$\mathbf{S}=\left[\begin{array}{cccc}\hfill s_1\hfill & \hfill 0\hfill & \hfill \dots \hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill s_2\hfill & \hfill \dots \hfill & \hfill 0\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \hfill & \hfill ⋮\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill \dots \hfill & \hfill s_n\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill \dots \hfill & \hfill 0\hfill \\ \hfill ⋮\hfill & \hfill ⋮\hfill & \hfill \hfill & \hfill ⋮\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill \dots \hfill & \hfill 0\hfill \end{array}\right]$

The singular values are the non-negative square roots of the eigenvalues of ${\mathbf{A}}^{\mathsf{T}}\mathbf{A}$ . Because ${\mathbf{A}}^{\mathsf{T}}\mathbf{A}$ is symmetric or Hermitian these eigenvalues are real and non-negative so that the singular values are also real and non-negative. Algorithms for computing the SVD of a matrix are given by Golub and Van Loan (1989).

The SVD of a matrix has several important applications. In Section 2.4 , we introduced the reduced row echelon form of a matrix and explained how the Matlab function rref gave information from which the rank of a matrix can be deduced. However, rank can be more effectively determined from the SVD of a matrix since its rank is equal to the number of its non-zero singular values. Thus, for a $5\times 5$ matrix of rank 3, $s_4$ and $s_5$ would be zero. In practice, rather than counting the non-zero singular values, Matlab determines rank from the SVD by counting the number of singular values greater than some tolerance value. This is a more realistic approach to determining rank than counting any non-zero value, however small.

To illustrate how singular value decomposition helps us to examine the properties of a matrix we will use the Matlab function svd to carry out a singular value decomposition and compare it with the function rref. Consider the following example in which a Vandermonde matrix is created using the Matlab function vander. The Vandermonde matrix is known to be ill-conditioned. SVD allows us to examine the nature of this ill-conditioning. In particular a zero or a very small singular value indicates rank deficiency and this example shows that the singular values are becoming relatively close to this condition. In addition SVD allows us to compute the condition number of the matrix. In fact, the Matlab function cond uses SVD to compute the condition number and this gives the same values as obtained by dividing the largest singular value by the smallest singular value. Additionally, the Euclidean norm of the matrix is supplied by the first singular value. Comparing the SVD with the RREF process in the following script, we see that the result of using the Matlab functions rref and rank give the rank of this special Vandermonde matrix as 5 but tells us nothing else. There is no warning that the matrix is badly conditioned.

>> c = [1 1.01 1.02 1.03 1.04];

>> V = vander(c)

V =

1.0000   1.0000   1.0000   1.0000   1.0000

1.0406   1.0303   1.0201   1.0100   1.0000

1.0824   1.0612   1.0404   1.0200   1.0000

1.1255   1.0927   1.0609   1.0300   1.0000

1.1699   1.1249   1.0816   1.0400   1.0000

>> format long

>> s = svd(V)

s =

5.210367051037899

0.101918335876689

0.000699698839445

0.000002352380295

0.000000003294983

>> norm(V)

ans =

5.210367051037898

>> cond(V)

ans =

1.581303244929480e+09

>> s(1)/s(5)

ans =

1.581303244929480e+09

>> rank(V)

ans =

5

>> rref(V)

ans =

1   0   0   0   0

0   1   0   0   0

0   0   1   0   0

0   0   0   1   0

0   0   0   0   1

The following example is very similar to the preceding one but the Vandermonde matrix has now been generated to be rank deficient. The smallest singular value, although not zero, is zero to machine precision and rank returns the value of 4.

>> c = [1 1.01 1.02 1.03 1.03];

>> V = vander(c)

V =

1.0000   1.0000   1.0000   1.0000   1.0000

1.0406   1.0303   1.0201   1.0100   1.0000

1.0824   1.0612   1.0404   1.0200   1.0000

1.1255   1.0927   1.0609   1.0300   1.0000

1.1255   1.0927   1.0609   1.0300   1.0000

>> format long e

>> s = svd(V)

s =

5.187797954424026e+00

8.336322098941423e-02

3.997349250041025e-04

8.462129966394409e-07

1.261104176071465e-23

>> format short

>> rank(V)

ans =

4

>> rref(V)

ans =

1.0000   0   0   0   -0.9424

0   1.0000   0   0   3.8262

0   0   1.0000   0   -5.8251

0   0   0   1.0000   3.9414

0   0   0   0   0

>> cond(V)

ans =

4.1137e+23

The rank function does allow the user to vary the tolerance using a second parameter, that is rank(A,tol) where tol gives the tolerance for acceptance of the singular values of A to be taken as non-zero. However, tolerance should be used with care since the rank function counts the number of singular values greater than tolerance and this gives the rank of the matrix. If tolerance is very small, that is, smaller than the machine precision, the rank may be miscounted.

Read full chapter

URL:

https://www.sciencedirect.com/science/article/pii/B9780128122563000117

Finding Set of Solutions From Rref

Source: https://www.sciencedirect.com/topics/mathematics/reduced-row-echelon-form

Share :