Bases and Dimension

Section 15 Bases and Dimension

Focus Questions

By the end of this section, you should be able to give precise and thorough answers to the questions listed below. You may want to keep these questions in mind to focus your thoughts as you complete the section

What is the dimension of a subspace of $R^{n} ?$ What property of bases makes the dimension a well-defined number?
If $W$ is a subspace of $R^{n}$ with dimension $k,$ what must be true about any linearly independent subset $S$ of $W$ that contains exactly $k$ vectors?
If $W$ is a subspace of $R^{n}$ with dimension $k,$ what must be true about any subset $S$ of $W$ that contains exactly $k$ vectors and spans $W ?$
What is the rank of a matrix?
What does the Rank-Nullity Theorem say?

🔗

Subsection Application: Lattice Based Cryptography

🔗

When you use your credit card, you expect that the information that is transmitted is protected so others can't use your card. Similarly, when you create a password for your computer or other devices, you do so with the intention that it will be difficult for others to decipher.

🔗

Cryptology is the study of methods to maintain secure communication in the presence of other parties (cryptography), along with the study of breaking codes (cryptanalysis). In essence, cryptology is the art of keeping and breaking secrets. The creation of secure codes (cryptography) can provide confidentiality (ensure that information is available only to the intended recipients), data integrity (prevent data from being altered between the sender and recipient), and authentication (making sure that the information is from the correct source).

🔗

Modern cryptology uses mathematical theory that can be implemented with computer hardware and algorithms. The security of public key systems is largely based on mathematical problems that are very difficult to solve. For example, the security of the RSA system relies on the fact that it is computationally difficult to find prime factors of very large numbers, and elliptic curve cryptography relies on the difficulty of the discrete logarithm problem for elliptic curves. However, the continual increase in the power of computers threatens the security of these systems, and so cryptographic systems have to keep adapting to the newest technology. For example, Shor's Algorithm (which could run on a quantum computer) can solve the public key cryptographic systems that rely on the integer factorization problem or the discrete logarithm problem. So if a working quantum computer was ever developed, it would threaten the existing cryptographic systems. Lattice-based cryptography is a potential source of systems that may be secure even in such an environment. The security of these systems is dependent on the fact that the average case of the difficulty of certain problems in lattice theory is higher than the worst case problems that underpin current cryptosystems. As we will see later in this section, lattices are built on bases for subspace of

R^{n} .

🔗

Subsection Introduction

🔗

A basis provides a system in which we can uniquely represent every vector in the space we are considering. More specifically, every vector in the space can be expressed as a linear combination of the vectors in the basis in a unique way. In order to be able to cover every point in the space, the basis has to span the space. In order to be able to provide a unique coordinate for each point, there should not be any extra vectors in the basis, which is achieved by linear independence of the vectors. For practical reasons, a basis simplifies many problems because we only need to solve the problem for each of the basis vectors. Solutions of the other cases usually follow because every vector in the space can be expressed as a unique linear combination of the basis vectors.

🔗

Recall that a basis for a subspace

W

R^{n}

is a set of vectors which are linearly independent and which span

W .

🔗

Preview Activity 15.1.

🔗

(a)

For each of the following sets of vectors, determine whether the vectors form a basis of $R^{3} .$ Use any appropriate technology for your computations.

🔗

(i)

${[\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}], [\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}], [\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}]}$

🔗

(ii)

${[\begin{matrix} 1 \\ 0 \\ 1 \end{matrix}], [\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}], [\begin{matrix} 2 \\ 3 \\ 1 \end{matrix}]}$

🔗

(iii)

${[\begin{matrix} 1 \\ 0 \\ 1 \end{matrix}], [\begin{matrix} 1 \\ 1 \\ 1 \end{matrix}], [\begin{matrix} 0 \\ 3 \\ 3 \end{matrix}], [\begin{array}{r} - 1 \\ 2 \\ 1 \end{array}]}$

🔗

(iv)

${[\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}], [\begin{matrix} 0 \\ 1 \\ 0 \end{matrix}]}$

🔗

(b)

In problem (1) we should have noticed that a space can have more than one basis, but that any two bases contain the same number of elements. This is a critically important idea that we investigate in more detail in this problem in one specific case. Assume that $W$ is a subspace of $R^{n}$ that has a basis $B = {v_{1}, v_{2}}$ with two basis vectors. We want to see if any other basis for $W$ can have a different number of elements. Let us now consider a set $U = {u_{1}, u_{2}, u_{3}}$ of three vectors in $W .$ Our goal is to determine if $U$ can be a basis for $W .$ Since $B$ is a basis for $W,$ any vector in $W$ can be written as a linear combination of the vectors in $B .$ So we can write

\begin{aligned} (15.1) & u_{1} & = a_{11} v_{1} + a_{21} v_{2} \\ (15.2) & u_{2} & = a_{12} v_{1} + a_{22} v_{2} \\ (15.3) & u_{3} & = a_{13} v_{1} + a_{23} v_{2} \end{aligned}

for some scalars $a_{i j} .$ If $U$ were to be a basis for $W,$ then $U$ would have to be a linearly independent set. To determine the independence or dependence of $U$ we consider the vector equation

\begin{matrix} (15.4) & x_{1} u_{1} + x_{2} u_{2} + x_{3} u_{3} = 0 \end{matrix}

for scalars $x_{1},$ $x_{2},$ and $x_{3} .$

🔗

(i)

Substitute for $u_{1},$ $u_{2},$ and $u_{3}$ from (15.1), (15.2), and (15.3) into (15.4) and perform some vector algebra to show that

\begin{matrix} (15.5) & 0 = (a_{11} x_{1} + a_{12} x_{2} + a_{13} x_{3}) v_{1} + (a_{21} x_{1} + a_{22} x_{2} + a_{23} x_{3}) v_{2} . \end{matrix}

🔗

(ii)

Recall that $B = {v_{1}, v_{2}}$ is a basis. What does that tell us about the weights in the linear combination (15.5)? Explain why $A x = 0,$ where $A = [a_{i j}]$ and $x = [x_{1} x_{2} x_{3}]^{T} .$

🔗

(iii)

With $A$ as in part (b), how many solutions does the system $A x = 0$ have? Explain. What does this tell us about the independence or dependence of the set $U ?$ Why?

Hint.

Consider the number of rows and columns of $A .$

🔗

(iv)

Can $U$ be a basis for $W ?$ Explain.

🔗

Subsection The Dimension of a Subspace of $R^{n}$

🔗

In Preview Activity 15.1 we saw that a subspace of

R^{n}

can have more than one basis. This prompts the question of how, if at all, are any two bases for a given space related. More specifically, is it possible to have two bases for a given subspace of

R^{n}

that contain different numbers of vectors? As we will see the answer is no, which will lead us to the concept of dimension.

🔗

Let

W

be a subspace of

R^{n}

that has a basis

B = {v_{1}, v_{2}, \dots, v_{k}}

k

vectors. Since we have been calling bases minimal spanning sets, we should expect that any two bases for the same subspace have the same number of elements (otherwise one of the two bases would not be minimal). Our goal in this section is to prove that result — that any other basis of

W

contains exactly

k

vectors. The approach will be the same as was used in Preview Activity 15.1. We will let

U = {u_{1}, u_{2}, \dots, u_{m}}

be a set of vectors in

W

with

m > k

and demonstrate that

U

is a linearly dependent set. To argue linear dependence, let

x_{1},

x_{2},

\dots,

x_{m}

be scalars so that

\begin{matrix} (15.6) & x_{1} u_{1} + x_{2} u_{2} + \dots + x_{m} u_{m} = 0 . \end{matrix}

🔗

For each

i

there exist scalars

a_{i j}

so that

u_{i} = a_{1 i} v_{1} + a_{2 i} v_{2} + \dots + a_{k i} v_{k} .

🔗

Substituting into (15.6) yields

\begin{aligned} 0 & = x_{1} u_{1} + x_{2} u_{2} + \dots + x_{m} u_{m} \\ = x_{1} (a_{11} v_{1} + a_{21} v_{2} + \dots + a_{k 1} v_{k}) + x_{2} (a_{12} v_{1} + a_{22} v_{2} \\ + \dots + a_{k 2} v_{k}) + \dots + x_{m} (a_{1 m} v_{1} + a_{2 m} v_{2} + \dots + a_{k m} v_{k}) \\ = (x_{1} a_{11} + x_{2} a_{12} + x_{3} a_{13} + \dots + x_{m} a_{1 m}) v_{1} \\ + (x_{1} a_{21} + x_{2} a_{22} + x_{3} a_{23} + \dots + x_{m} a_{2 m}) v_{2} \\ (15.7) & + \dots + (x_{1} a_{k 1} + x_{2} a_{k 2} + x_{3} a_{k 3} + \dots + x_{m} a_{k m}) v_{k} . \end{aligned}

🔗

Since

B

is a basis, the vectors

v_{1},

v_{2},

\dots,

v_{k}

are linearly independent. So each coefficient in (15.7) is 0 and

x = [x_{1} x_{2} \dots x_{m}]^{T}

is a solution to the homogeneous system

A x = 0,

where

A = [a_{i j}] .

Now

A

is a

k \times m

matrix with

m > k,

so not every column of

A

is a pivot column. This means that

A x = 0

has a nontrivial solution. It follows that the vector equation (15.6) has a nontrivial solution and so the

m

vectors

u_{1},

u_{2},

\dots,

u_{m}

are linearly dependent. We summarize this in the following theorem.

🔗

Theorem 15.1.

Let $W$ be a subspace of $R^{n}$ containing a basis with $k$ vectors. If $m > k,$ then any set of $m$ vectors in $W$ is linearly dependent.

🔗

One consequence of Theorem 15.1 is that, in addition to being a minimal spanning set, a basis is also a maximal linearly independent set.

🔗

Activity 15.2.

Now let's return to the question of the number of elements in a basis for a subspace of $R^{n} .$ Recall that we are assuming that $W$ has a basis $B = {v_{1}, v_{2}, \dots, v_{k}}$ of $k$ vectors in $R^{n} .$ Suppose that $B^{'}$ is another basis for $W$ containing $m$ vectors.

🔗

(a)

Given the fact that $B$ is a basis for $W,$ what does Theorem 15.1 tell us about the relationship between $m$ and $k ?$

🔗

(b)

Given the fact that $B^{'}$ is a basis for $W,$ what does Theorem 15.1 tell us about the relationship between $m$ and $k ?$

🔗

(c)

What do the results of (a) and (b) tell us about the relationship between $m$ and $k ?$ What can we conclude about any basis for $W ?$

🔗

The result of Activity 15.2 is summarized in the following theorem. Recall that the trivial space is the single element set

{0} .

🔗

Theorem 15.2.

If a nontrivial subspace $W$ of $R^{n}$ has a basis of $k$ vectors, then every basis of $W$ contains exactly $k$ vectors.

🔗

This last theorem states that the number of vectors in a basis for a subspace space is a well-defined number. In other words, the number of vectors in a basis is an invariant of the subspace. This important number is given a name.

🔗

Definition 15.3.

The dimension of a subspace $W$ of $R^{n}$ is the number of vectors in a basis for $W .$ The dimension of the trivial subspace ${0}$ of $R^{n}$ is defined to be 0.

🔗

We denote the dimension of a subspace

W

R^{n}

\dim (W) .

As we will see later, any two vector spaces of the same dimension are basically the same vector space. So the dimension of a vector space is an important number that essentially tells us all we need to know about the structure of the space.

🔗

Activity 15.3.

Find the dimensions of each of the indicated subspaces of $R^{n}$ for the appropriate $n .$ Explain your method.

🔗

(a)

$Span {[\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}], [\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}], [\begin{matrix} 2 \\ 3 \\ 0 \end{matrix}]}$

🔗

(b)

$x y$ -plane in $R^{3}$

🔗

(c)

$R^{3}$

🔗

(d)

$R^{n}$

🔗

Subsection Conditions for a Basis of a Subspace of $R^{n}$

🔗

There are two items we need to confirm before we can state that a subset

B

of a subspace

W

R^{n}

is a basis for

W :

the set

B

must be linearly independent and span

W .

However, if we have the right number (namely, the dimension) of vectors in our set

B,

then either one of these conditions will imply the other.

🔗

Activity 15.4.

Let $W$ be a subspace of $R^{n}$ with $\dim (W) = k .$ We know that every basis of $W$ contains exactly $k$ vectors.

🔗

(a)

Suppose that $S$ is a subset of $W$ that contains $k$ vectors and is linearly independent. In this part of the activity we will show that $S$ must span $W .$

🔗

(i)

Suppose that $S$ does not span $W .$ Explain why this implies that $W$ contains a set of $k + 1$ linearly independent vectors.

🔗

(ii)

Explain why the result of part i. tells us that $S$ is a basis for $W .$

🔗

(b)

Now suppose that $S$ is a subset of $W$ with $k$ vectors that spans $W .$ In this part of the activity we will show that $S$ must be linearly independent.

🔗

(i)

Suppose that $S$ is not linearly independent. Explain why we can then find a proper subset of $S$ that is linearly independent but has the same span as $S .$

🔗

(ii)

Explain why the result of part i. tells us that $S$ is a basis for $W .$

🔗

The result of Activity 15.4 is the following important theorem.

🔗

Theorem 15.4.

Let $W$ be a subspace of $R^{n}$ of dimension $k$ and let $S$ be a subset of $W$ containing exactly $k$ vectors.

If $S$ is linearly independent, then $S$ is a basis for $W .$
If $S$ spans $W,$ then $S$ is a basis for $W .$

🔗

Subsection Finding a Basis for a Subspace

🔗

Since every vector in a subspace of

R^{n}

can be written uniquely as a linear combination of vectors in a basis for the subspace, a basis provides us with the most efficient and convenient way to represent vectors in the subspace. Until now we have been given a set of vectors and have been asked to find a basis from that set, so an important question to address is how we can find a basis for a subspace

W

R^{n}

starting from scratch. Here is one way. If

W = {0},

then the dimension of

W

is 0 and

W

has no basis. So suppose

\dim (W) > 0 .

Start by choosing any nonzero vector

w_{1}

W .

Let

B_{1} = {w_{1}} .

B_{1}

spans

W,

then

B_{1}

is a basis for

W .

If not, there is a vector

w_{2}

W

that is not in

Span (B_{1}) .

Then

B_{2} = {w_{1}, w_{2}}

is a linearly independent set. If

Span (B_{2}) = W,

then

B_{2}

is a basis for

W

and we are done. If not, repeat the process. Since any basis for

W

can contain at most

n = \dim (R^{n})

vectors, we know the process must stop at some point. This process also allows us to construct a basis for a vector space that contains a given nonzero vector.

🔗

Activity 15.5.

Find a basis for $R^{3}$ that contains the vector $[\begin{array}{r} 1 \\ 2 \\ - 1 \end{array}] .$ When constructing your basis, how do you know when to stop?

🔗

Subsection Rank of a Matrix

🔗

In this section, we define the rank of a matrix and review conditions to add to our Invertible Matrix Theorem.

🔗

Activity 15.6.

Let $A = [\begin{array}{rrrrr} 1 & 2 & - 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & - 1 \\ 0 & 0 & 0 & 1 & 1 \end{array}] .$

🔗

(a)

Without performing any calculations, find $\dim (Nul A) .$ Explain.

🔗

(b)

Without performing any calculations, find $\dim (Col A) .$ Explain.

🔗

(c)

There is a connection between $\dim (Nul A),$ $\dim (Col A)$ and the size of $A .$ Find this connection and explain it.

🔗

As Activity 15.6 illustrates, the number of vectors in a basis for

Nul A

is the number of non-pivot columns in

A

and the number of vectors in a basis for

Col A

is the number of pivot columns of

A .

We define the rank of a matrix

A

(denoted rank(

A

)) to be the dimension of

Col A

and the nullity of

A

to be dimension of

Nul A .

The dimension of the null space of

A

is also called the nullity of

A

(denoted nullity(

A

)) Using this terminology we have the Rank-Nullity Theorem.

🔗

Theorem 15.5. The Rank-Nullity Theorem.

Let $A$ be an $m \times n$ matrix. Then

rank (A) + nullity (A) = n .

🔗

There is also a row space of a matrix

A,

which we define to be the span of the rows of

A .

We can find the row space of

A

by finding the column space of

A^{T},

so the row space is really nothing new. As it turns out, the dimension of the row space of

A

is always equal to the dimension of the column space of

A,

and justification for this statement is in the exercises.

🔗

The Rank-Nullity Theorem allows us to add extra conditions to the Invertible Matrix Theorem.

🔗

Theorem 15.6. The Invertible Matrix Theorem.

Let $A$ be an $n \times n$ matrix. The following statements are equivalent.

The matrix $A$ is an invertible matrix.
The matrix equation $A x = 0$ has only the trivial solution.
The matrix $A$ has $n$ pivot columns.
Every row of $A$ contains a pivot.
The columns of $A$ span $R^{n} .$
The matrix $A$ is row equivalent to the identity matrix $I_{n} .$
The columns of $A$ are linearly independent.
The columns of $A$ form a basis for $R^{n} .$
The matrix transformation $T$ from $R^{n}$ to $R^{n}$ defined by $T (x) = A x$ is one-to-one.
The matrix equation $A x = b$ has exactly one solution for each vector $b$ in $R^{n} .$
The matrix transformation $T$ from $R^{n}$ to $R^{n}$ defined by $T (x) = A x$ is onto.
There is an $n \times n$ matrix $C$ so that $A C = I_{n} .$
There is an $n \times n$ matrix $D$ so that $D A = I_{n} .$
The scalar 0 is not an eigenvalue of $A .$
The matrix $A^{T}$ is invertible.
$Nul A = {0} .$
$Col A = R^{n} .$
$\dim (Col A) = n$
$\dim (Nul A) = 0$
$rank (A) = n$

🔗

Subsection Examples

🔗

What follows are worked examples that use the concepts from this section.

🔗

Example 15.7.

Let $W = {[\begin{matrix} r + s + u \\ r + 3 s + 2 t - u \\ - s - t + u \\ s + t - u \end{matrix}] : r, s, t, u \in R} .$

🔗

(a)

Explain why $W$ is a subspace of $R^{4} .$

Solution.

We can write any vector in $W$ in the form

[\begin{matrix} r + s + u \\ r + 3 s + 2 t - u \\ - s - t + u \\ s + t - u \end{matrix}] = r [\begin{matrix} 1 \\ 1 \\ 0 \\ 0 \end{matrix}] + s [\begin{array}{r} 1 \\ 3 \\ - 1 \\ 1 \end{array}] + t [\begin{array}{r} 0 \\ 2 \\ - 1 \\ 1 \end{array}] + u [\begin{array}{r} 1 \\ - 1 \\ 1 \\ - 1 \end{array}],

W = Span {[\begin{matrix} 1 \\ 1 \\ 0 \\ 0 \end{matrix}], [\begin{array}{r} 1 \\ 3 \\ - 1 \\ 1 \end{array}], [\begin{array}{r} 0 \\ 2 \\ - 1 \\ 1 \end{array}], [\begin{array}{r} 1 \\ - 1 \\ 1 \\ - 1 \end{array}]} .

As a span of a set of vectors in $R^{4},$ $W$ is a subspace of $R^{4} .$

🔗

(b)

Find a basis for $W$ and determine the dimension of $W .$

Solution.

Let $A = [\begin{array}{crrr} 1 & 1 & 0 & 1 \\ 1 & 3 & 2 & - 1 \\ 0 & - 1 & - 1 & 1 \\ 0 & 1 & 1 & - 1 \end{array}] .$ To find a basis for $W,$ we note that the reduced row echelon form of $A$ is $[\begin{array}{ccrr} 1 & 0 & - 1 & 2 \\ 0 & 1 & 1 & - 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array}] .$ Since the pivot columns of $A$ form a basis for $Col A = W,$ we conclude that

{[\begin{matrix} 1 \\ 1 \\ 0 \\ 0 \end{matrix}], [\begin{array}{r} 1 \\ 3 \\ - 1 \\ 1 \end{array}]}

is a basis for $W .$ Therefore, $\dim (W) = 2 .$

🔗

Example 15.8.

Find a basis and the dimension of the solution set to the system

\begin{aligned} r & + & s & - & t & + & 2 u & = 0 \\ 3 r & - & s & + & 2 t & - & u & = 0 \\ r & - & 3 s & + & 4 t & - & 5 u & = 0 \\ r & - & 3 s & + & 5 t & - & 4 u & = 0 & . . \end{aligned}

Solution.

The coefficient matrix of this system is

A = [\begin{array}{crrr} 1 & 1 & - 1 & 2 \\ 3 & - 1 & 2 & - 1 \\ 1 & - 3 & 4 & - 5 \\ 5 & - 3 & 5 & - 4 \end{array}],

and the solution set to the system is $Nul A .$ To find a basis for $Nul A$ we row reduce $A$ to

[\begin{array}{ccrc} 1 & 0 & \frac{1}{4} & \frac{1}{4} \\ 0 & 1 & - \frac{5}{4} & \frac{7}{4} \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array}] .

The general solution to the system has the form

[\begin{matrix} r \\ s \\ t \\ u \end{matrix}] = [\begin{matrix} - \frac{1}{4} t - \frac{1}{4} u \\ \frac{5}{4} t - \frac{7}{4} u \\ t \\ u \end{matrix}] = t [\begin{array}{r} - \frac{1}{4} \\ \frac{5}{4} \\ 1 \\ 0 \end{array}] + u [\begin{array}{r} - \frac{1}{4} \\ - \frac{7}{4} \\ 0 \\ 1 \end{array}],

so ${[\begin{array}{r} - \frac{1}{4} \\ \frac{5}{4} \\ 1 \\ 0 \end{array}], [\begin{array}{r} - \frac{1}{4} \\ - \frac{7}{4} \\ 0 \\ 1 \end{array}]}$ is a basis for $Nul A$ and $\dim (Nul A) = 2 .$

🔗

Subsection Summary

🔗

The key idea in this section is the dimension of a vector space.

Any two bases for a vector space must contain the same number of vectors. Therefore, we can define the dimension of a vector space $W$ to be the number of vectors in any basis for $W .$
If $W$ is a subspace of $R^{n}$ with dimension $k$ and $S$ is any linearly independent subset of $W$ with $k$ vectors, then $S$ is a basis for $W .$
If $W$ is a subspace of $R^{n}$ with dimension $k$ and $S$ is any subset of $W$ with $k$ vectors that spans $W,$ then $S$ is a basis for $W .$
The rank of a matrix is the dimension of its column space.
The Rank-Nullity Theorem states that if $A$ is an $m \times n$ matrix, then $rank (A) + nullity (A) = n .$

🔗

Exercises Exercises

🔗

1.

Let $A = [\begin{array}{ccccr} 1 & 3 & 1 & 2 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 2 & 6 & 0 & 0 & 1 \\ 1 & 3 & 2 & 4 & 1 \\ 3 & 9 & 1 & 2 & - 1 \\ 3 & 9 & 3 & 6 & 1 \end{array}] .$

🔗

(a)

Find a basis for $Col A .$ What is the dimension of $Col A ?$ What, then, is the dimension of $Nul A ?$

🔗

(b)

Find a basis for $Nul A$ and verify the dimension you found in part (a).

🔗

2.

Let $A = [\begin{array}{crc} 2 & - 1 & 1 \\ 1 & 0 & 1 \\ 1 & - 1 & 2 \end{array}] .$ The eigenvalues of $A$ are $1$ and $2 .$ Find the dimension of each eigenspace of $A .$

🔗

3.

Let $A = [\begin{array}{rrrr} 1 & 2 & - 1 & - 1 \\ - 2 & - 4 & 2 & 2 \\ 1 & 2 & - 1 & - 1 \end{array}] .$

🔗

(a)

Find a basis for $Col A .$ What is the rank of $A ?$

🔗

(b)

Find a basis for $Nul A .$ What is the nullity of $A .$

🔗

(c)

Verify the Rank-Nullity Theorem for $A .$

🔗

(d)

The row space of $A$ is the span of the rows of $A .$ Find a basis for the row space of $A$ and the dimension of the row space of $A .$

🔗

4.

Let $A$ be an $m \times n$ matrix with $r$ pivots, where $r$ is less than or equal to both $m, n .$ Fill in the blanks.

🔗

(a)

The null space of $A$ is a subspace of .

🔗

(b)

The column space of $A$ is a subspace of .

🔗

(c)

Suppose $r = m .$ Then there is a pivot in every and $Col A =$ .

🔗

(d)

Suppose $r = n .$ Then there is a pivot in every and $Nul A =$ .

🔗

(e)

If $A$ has 3 pivots, then the rank of $A$ is .

🔗

(f)

If $A$ has 3 pivots, then the number of free variables in the system $A x = 0$ is .

🔗

(g)

The dimension of $Col A$ is equal to the number of , i.e. $\dim Col A =$ .

🔗

(h)

The dimension of $Nul A$ is equal to the number of , i.e. $\dim Nul A =$ .

🔗

(i)

$\dim (Nul A) + \dim (Col A) =$ .

🔗

(j)

Suppose the columns of $A$ span $R^{m} .$ Then rank $A$ is .

🔗

(k)

Suppose the columns of $A$ are linearly independent. Then $r =$ and the dimension of $Nul A$ is .

🔗

5.

Prove the remaining parts of the Invertible Matrix Theorem (Theorem 15.6). Let $A$ be an $n \times n$ matrix.

🔗

(a)

Prove that $A$ is invertible if and only if $\dim (Nul A) = 0 .$

Hint.

What are the solutions to $A x = 0 ?$

🔗

(b)

Prove that $A$ is invertible if and only if $\dim (Col A) = n .$

Hint.

Use part (a) and the Rank-Nullity Theorem.

🔗

6.

We can convert the language of the Rank-Nullity Theorem to matrix transformation language, as we show in this exercise. Let $T$ be the matrix transformation defined by the matrix $A .$

🔗

(a)

How is the kernel of $T$ related to $A ?$

🔗

(b)

How is the range of $T$ related to $A ?$

🔗

(c)

How is the domain of $T$ related to $A ?$

🔗

(d)

Explain why the Rank-Nullity Theorem says that $\dim (Ker (T)) + \dim (Range (T)) = \dim (Domain (T)) .$

🔗

7.

Let $W$ be a subspace of $R^{4} .$ What are possible values for the dimension of $W ?$ Explain. What are the geometric descriptions of $W$ in each case?

🔗

8.

Is it possible to find two subspaces $W_{1}$ and $W_{2}$ in $R^{3}$ such that $W_{1} \cap W_{2} = {0}$ and $\dim W_{1} = \dim W_{2} = 2 ?$ If possible, give an example and justify that they satisfy the conditions. If not possible, explain why not.

Hint.

Dimension two leads to two linearly independent vectors in each of $W_{i} .$

🔗

9.

Determine the dimensions of the column space and null space of $[\begin{array}{ccccc} 1 & 2 & 4 & 3 & 2 \\ 1 & 0 & 2 & 1 & 4 \\ 1 & 1 & 3 & 1 & 2 \\ 1 & 0 & 2 & 2 & 5 \end{array}] .$

🔗

10.

If possible, find a $3 \times 4$ matrix whose column space has dimension 3 and null space has dimension 1. Explain how you found the matrix in addition to explaining why your answer works. If not possible, explain why it is not possible to find such a matrix.

🔗

11.

🔗

(a)

If possible, find a $5 \times 5$ matrix whose column space has the same dimension as its null space. Explain how you found the matrix in addition to explaining why your answer works. If not possible, explain why it is not possible to find such a matrix.

🔗

(b)

If possible, find a matrix $A$ so that $Col A = Nul A .$ Explain how you found the matrix in addition to explaining why your answer works. If not possible, explain why it is not possible to find such a matrix.

🔗

12.

In this exercise we examine why the dimension of a row space of a matrix is the same as the dimension of the column space of the matrix. Let $A$ be an $m \times n$ matrix.

🔗

(a)

Explain why row operations do not change the row space of a matrix. Then explain why if $R$ is the reduced row echelon form of $A,$ then $Row R = Row A,$ where $Row M$ is the row space of the matrix $M .$

🔗

(b)

Explain why the rows of $R$ that contain pivots form a basis for $Row R,$ and also of $Row A .$

🔗

(c)

Explain why $rank (A)$ is the number of pivots in the matrix $A .$ Then explain why $\dim (Row A) = \dim (Col A) .$

🔗

13.

Label each of the following statements as True or False. Provide justification for your response.

🔗

(a) True/False.

The dimension of the column space of a $3 \times 2$ matrix can be three.

🔗

(b) True/False.

There exists a $3 \times 3$ matrix whose column space has equal dimension as the null space.

🔗

(c) True/False.

If a set of vectors spans a subspace, then that set is a basis of this subspace.

🔗

(d) True/False.

If a linearly independent set of vectors spans a subspace, then that set is a basis of this subspace.

🔗

(e) True/False.

The dimension of a space is the minimum number of vectors needed to span that space.

🔗

(f) True/False.

The dimension of the null space of a $3 \times 2$ matrix can at most be 2.

🔗

(g) True/False.

Any basis of $R^{4}$ contains 4 vectors.

🔗

(h) True/False.

If $n$ vectors span $R^{n},$ then these vectors form a basis of $R^{n} .$

🔗

(i) True/False.

Every line in $R^{n}$ is a one-dimensional subspace of $R^{n} .$

🔗

(j) True/False.

Every plane through origin in $R^{n}$ is a two-dimensional subspace of $R^{n} .$

🔗

(k) True/False.

In $R^{n}$ any $n$ linearly independent vectors form a basis.

🔗

Subsection Project: The GGH Cryptosystem

🔗

A cryptographic system (or cryptosystem) allows for secure communication between two or more parties. These systems take messages (called plaintext) and encrypt them in some way to produce what is called ciphertext. This is the scrambled information that is transmitted to the receiver, from which it should not be possible for someone who does not have the proper key to recover the original message. When the message is received by the intended recipient, it must be unscrambled or decrypted. Decryption is the process of converting ciphertext back to plaintext.

🔗

The Goldreich-Goldwasser-Halevi (GGH) public key cryptosystem³⁰ uses lattices to encrypt plaintext. The security of the system depends on the fact that the Closest Vector Problem (CVP) is, in general, a very hard problem. To begin to understand these cryptosystems, we begin with lattices.

🔗

Lattices are closely related to spans of sets of vectors in

R^{n} .

If we start with a linearly independent set

S = {b_{1}, b_{2}, \dots, b_{m}}

R^{n},

we can create the span of

S

— the set of all linear combinations

c_{1} b_{1} + c_{2} b_{2} + \dots + c_{m} b_{m},

🔗

where

c_{1},

c_{2},

\dots,

c_{m}

are real numbers. This span creates a subspace of

R^{n} .

If we restrict the set from which we choose the coefficients, we can create different types of structures. An important one is a lattice. The lattice

L (S)

defined by the linearly independent set

S = {b_{1}, b_{2}, \dots, b_{m}}

is the set of linear combinations

c_{1} b_{1} + c_{2} b_{2} + \dots + c_{m} b_{m},

🔗

where

c_{1},

c_{2},

\dots,

c_{m}

are integers. If the vectors in

S

have integer components, then every point in

L (S)

will have integer entries. In these cases,

L (S)

is a subset of

Z^{n},

as illustrated in Figure 15.9. Also, if

m = n

we say that the lattice

L (S)

is full-rank. We will restrict ourselves to full-rank lattices in this project. A basis for a lattice is any set of linearly independent vectors that generates the lattice. There is a little special notation that is often used with lattices. If

B = {b_{1}, b_{2}, \dots, b_{n}}

is a basis for

R^{n},

we associate to

B

the matrix

B = [b_{1} b_{2} b_{3} \dots b_{n}] .

We then use the notation

L (B)

to also refer to the lattice defined by

B .

🔗

Project Activity 15.7.

We explore lattices in more detail in this activity.

🔗

(a)

Let $S_{1} = {[1 1]^{T}, [- 1 1]^{T}} .$

🔗

(i)

Find five distinct vectors in $L (S_{1}) .$

🔗

(ii)

Is the vector $[1 0]^{T}$ in $L (S_{1}) ?$ Justify your answer.

🔗

(iii)

We can draw pictures of lattices by plotting the terminal points of the lattice vectors. Draw all of the lattice points in $L (S_{1})$ on the square with vertices $(- 4, - 4),$ $(4, - 4),$ $(4, 4),$ and $(- 4, 4) .$

🔗

(b)

Now let $S_{2} = {[3 5]^{T}, [1 2]^{T}} .$ A picture of $L (S_{2})$ is shown in Figure 15.9 with the basis vectors highlighted. As we have seen, $L (S_{1})$ is not the entire space $Z^{2} .$ Is $L (S_{2}) = Z^{2} ?$ Justify your answer.

🔗

Project Activity 15.7 shows that even if

B

is a basis for

R^{n},

it does not follow that

L (B)

is all of

Z^{n} .

So latices can be complicated, and problems in lattice theory can be very difficult.

🔗

The GGH cryptosystem relies on the fact that we can convert “good” bases for lattices into “bad” bases. We will not delve into the details of what separates a “good” basis from a “bad” one, but suffice it to say that a good basis is one in which the basis vectors are close to being perpendicular³¹ and are all short (that is, they have small norms), while any other basis is a bad basis. An example of a good basis is the basis

S_{1}

for

R^{2}

in Project Activity 15.7, and we will see later that

{[- 2 8]^{T}, [- 1 3]^{T}}

is a bad basis for the same lattice. You should draw a picture of the vectors

[- 2 8]^{T}

and

[- 1 3]^{T}

to convince yourself that this is a bad basis for its lattice.

🔗

The GGH cryptosystem works with two keys — a public key and a private key. The keys are based on lattices. The general process of the GGH cryptosystem is as follows. Begin with a good basis

B = {b_{1} b_{2} \dots b_{n}}

R^{n}

of vectors with integer components. Let

B = [b_{1} b_{2} \dots b_{n}]

be the matrix associated with

B .

Let

B^{'} = {b_{1}^{'}, b_{2}^{'}, \dots, b_{n}^{'}}

be a bad basis for which

L (B^{'}) = L (B) .

Let

B^{'} = [b_{1}^{'} b_{2}^{'} \dots b_{n}^{'}]

be the matrix associated to the basis

B^{'} .

The bad basis can be shared with anyone (the public key), but the good basis is kept secret (the private key). Start with a message

m = [m_{1} m_{2} \dots m_{n}]^{T}

with integer entries to send.

🔗

First we encrypt the message, which can be done by anyone who has the public key

B^{'} .

Create the message vector

$m^{'} = m_{1} b_{1}^{'} + m_{2} b_{2}^{'} + \dots + m_{n} b_{n}^{'} = B^{'} m$

that is in the lattice using the bad basis $B^{'} .$
Choose a small error $e$ to add to $m^{'}$ to move $m^{'}$ off the lattice (small enough so that $m^{'}$ does not pass by another lattice point). This is an important step that will make the message difficult to decrypt without the key. Let $c = m^{'} + e = B^{'} m + e .$ The vector $c$ is the ciphertext that is to be transmitted to the receiver.

🔗

Only someone who knows the basis

B

can decode the ciphertext. This is done as follows.

Find the vector $a = a_{1} b_{1} + a_{2} b_{2} + \dots + a_{n} b_{n}$ in the good basis $B$ that is closest to $c .$
We interpret the vector $[a_{1} a_{2} \dots a_{n}]^{T}$ as being the encoded vector without the error. So to recreate the original message vector we need to undo the encrypting using the bad basis $B^{'} .$ That is, we need to find the weights $y_{1},$ $y_{2},$ $\dots,$ $y_{n}$ such that

$[a_{1} a_{2} \dots a_{n}]^{T} = y_{1} b_{1}^{'} + y_{2} b_{2}^{'} + \dots + y_{n} b_{n}^{'} = B^{'} [y_{1} y_{2} \dots y_{n}]^{T} .$

We can do this by as $[y_{1} y_{2} \dots y_{n}]^{T} = B^{' - 1} [a_{1} a_{2} \dots a_{n}]^{T} .$

🔗

There are several items to address before we can implement this algorithm. One is how we create a bad basis

B^{'}

from

B

that produces the same lattice. Another is how we find the vector in

B

closest to a given vector. The latter problem is called the Closest Vector Problem (CVP) and is, in general, a very difficult problem. This is what makes lattice-based cryptosystems secure. We address the first of these items in the next activity, and the second a bit later.

🔗

Project Activity 15.8.

Consider again the basis $S_{1} = {[1 1]^{T}, [- 1 1]^{T}}$ from Project Activity 15.7, and let $B = [\begin{array}{cr} 1 & - 1 \\ 1 & 1 \end{array}]$ be the matrix whose columns are the vectors in $S_{1} .$

🔗

(a)

Let $T$ be the triangle with vertices $(0, 0),$ $(1, 1),$ and $(- 1, 1) .$ Show that this triangle is a right triangle, and conclude that the vectors $v_{1} = [1 1]^{T},$ and $v_{2} = [- 1 1]^{T}$ are perpendicular.

🔗

(b)

Let $U = [\begin{array}{cc} 3 & 1 \\ 5 & 2 \end{array}] .$ Let $S_{3}$ be the set whose vectors are the columns of the matrix $B_{1} U .$ Show that $L (S_{1}) = L (S_{3}) .$

🔗

The two bases

S_{1} = {[1 1]^{T}, [- 1 1]^{T}}

and

S_{3} = {[- 2 8]^{T}, [- 1 3]^{T}}

from Project Activity 15.8 are shown in Figure 15.10. This figure illustrates how the matrix

U

transforms the basis

S_{1},

in which the vectors are perpendicular and short, to one in which the vectors are nearly parallel and significantly longer. So the matrix

U

converts the “good” basis

S_{1}

into a “bad” basis

S_{2},

keeping the lattice intact. This is a key idea in the GGH cryptosystem. What makes this work is the fact that both

U

and

U^{- 1}

have integer entries. The reason for this is that, for a

2 \times 2

matrix

U = [\begin{array}{cc} a & b \\ c & d \end{array}],

we know that

U^{- 1} = \frac{1}{a d - b c} [\begin{array}{rr} d & - b \\ - c & a \end{array}] .

U

has integer entries and

a d - b c = \pm 1,

then

U^{- 1}

will also have integer entries. The number

a d - b c

is called the determinant of

U,

and matrices with determinant of

1

- 1

are called unimodular. That what happened in Project Activity 15.8 happens in the general case is the focus of the next activity.

🔗
Figure 15.10. The lattices $L (S_{1})$ and $L (S_{3}) .$

🔗

Project Activity 15.9.

We will restrict ourselves to $2 \times 2$ matrices in this activity, but the results generalize to $n \times n$ matrices. Let $B = {b_{1}, b_{2}}$ and $B^{'} = {b_{1}^{'}, b_{2}^{'}}$ be bases for $R^{2}$ with integer entries, and let $B = [b_{1} b_{2}]$ and $B^{'} = [b_{1}^{'} b_{2}^{'}]$ be the matrices associated to these bases. Show that if $B^{'} = B U$ for some unimodular matrix $U$ with integer entries, then $L (B) = L (B^{'}) .$

🔗

Project Activity 15.9 is the part we need for our lattice-based cryptosysystem. Although we won't show it here, the converse of the statement in Project Activity 15.9 is also true. That is, if

B

and

B^{'}

generate the same lattice, then

B^{'} = B U

for some unimodular matrix

U

with integer entries.

🔗

There is one more item to address before we implement the GGH cryptosystem. That item is how to solve the Closest Vector Problem. There are some algorithms for approximating the closest vector in a basis. One is Babai's Closest Vector algorithm. This algorithm works in the following way. Consider a lattice with basis

{b_{1}, b_{2}, \dots, b_{n}} .

To approximate the closest vector in the lattice to a vector

w,

find the weights

c_{1},

c_{2},

\dots,

c_{n}

R

such that

w = c_{1} b_{1} + c_{2} b_{2} + \dots + c_{n} b_{n} .

Then round the coefficients to the nearest integer. This algorithm works well for a good basis, but is unlikely to return a lattice point that is close to

w

if the basis is a bad one.

🔗

Now we put this all together to illustrate the GGH algorithm.

🔗
Figure 15.11. Decrypting an encrypted message.

🔗

Project Activity 15.10.

Let $B = {[5 0]^{T}, [0 3]^{T}}$ be the private key, and let $B = [\begin{array}{cc} 5 & 0 \\ 0 & 3 \end{array}]$ be the matrix whose columns are the vectors in $B .$ Let $U$ be the unimodular matrix $U = [\begin{array}{cc} 2 & 3 \\ 3 & 5 \end{array}] .$ Let $m = [3 - 2]^{T}$ be our message and let $e = [1 - 1]^{T}$ be our error vector.

🔗

(a)

Use the unimodular matrix $U$ to create the bad basis $B^{'} .$

🔗

(b)

Determine the ciphertext message $c .$

🔗

(c)

A picture of the message vector $m$ and the ciphertext vector $c$ are shown in Figure 15.11. Although the closest vector in the lattice to $c$ can be determined by the figure, actual messages are constructed in high dimensional spaces where a visual approach is not practical. Use Babai's algorithm to find the vector in $L (B)$ that is closest to $c$ and compare to Figure 15.11.

🔗

(d)

The final step in the GGH scheme is to recover the original message. Complete the GGH algorithm to find this message.

🔗

(e)

The GGH cryptosystem works because the CVP can be reasonable solved using a good basis. That is, Babai's algorithm works if our basis is a good basis. To illustrate that a bad basis will not allow us to reproduce the original message vector, show that Babai's algorithm does not return the closest vector to $c$ using the bad basis $B^{'} .$

Published in 1997 by Oded Goldreich, Shafi Goldwasser, and Shai Halevi.

This is also a good property in vector spaces. We will see in a later section that perpendicular basis vectors make calculations in vector spaces relatively easy. A similar thing is true in lattices, where we are able to solve certain variants of closest vector problem very efficiently.

Section 15 Bases and Dimension

Focus Questions

Subsection Application: Lattice Based Cryptography

Subsection Introduction

Preview Activity 15.1.

(a)

(i)

(ii)

(iii)

(iv)

(b)

(i)

(ii)

(iii)

(iv)

Subsection The Dimension of a Subspace of Rn

Theorem 15.1.

Activity 15.2.

(a)

(b)

(c)

Theorem 15.2.

Definition 15.3.

Activity 15.3.

(a)

(b)

(c)

(d)

Subsection Conditions for a Basis of a Subspace of Rn

Activity 15.4.

(a)

(i)

(ii)

(b)

(i)

(ii)

Theorem 15.4.

Subsection Finding a Basis for a Subspace

Activity 15.5.

Subsection Rank of a Matrix

Activity 15.6.

(a)

(b)

(c)

Theorem 15.5. The Rank-Nullity Theorem.

Theorem 15.6. The Invertible Matrix Theorem.

Subsection Examples

Example 15.7.

(a)

Solution.

(b)

Solution.

Example 15.8.

Solution.

Subsection Summary

Exercises Exercises

1.

(a)

(b)

2.

3.

(a)

(b)

(c)

(d)

4.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j)

(k)

5.

(a)

(b)

Subsection The Dimension of a Subspace of $R^{n}$

Subsection Conditions for a Basis of a Subspace of $R^{n}$