An Inquiry-Based Introduction to Linear Algebra and Applications

Subsection Application: Secret Sharing Algorithms

Suppose we have a secret that we want or need to share with several individuals. For example, a bank manager might want to share pieces of the code for the bank vault with several employees so that if the manager is not available, some subset of these employees could open the vault if they work together. This allows for a significant amount of security while still making the code available if needed. As another example, in order to keep passwords secure (as they can be hard to remember), a person could implement a secret sharing scheme. The person would generate a set of shares for a given password and store them in several different places. If the person forgets the password, it can be reconstructed by collecting some set of these shares. Since the shares can be stored in many different places, the password is relatively secure.

The idea behind secret sharing algorithms is to break a secret into a number (\(n\)) of pieces and give each person one piece. A code is then created in such a way that any \(k\) individuals could combine their information and learn the secret, but no group of fewer than \(k\) individuals could. This is called a \((k,n)\) threshold scheme. One secret sharing algorithm is Shamir's Secret Sharing, which, as we will see later in this section, involves Lagrange polynomials. In order to implement this algorithm, we will use matrices of linear transformations from polynomials spaces to \(\R^n\text{.}\)

Subsection Introduction

A matrix transformation \(T\) from \(\R^n\) to \(\R^m\) is a linear transformation defined by \(T(\vx) = A\vx\) for some \(m \times n\) matrix \(A\text{.}\) We can use the matrix to quickly determine if \(T\) is one-to-one or onto — if every column of \(A\) contains a pivot, then \(T\) is one-to-one, and if every row of \(A\) contains a pivot, then \(T\) is onto. As we will see, we can represent any linear transformation between finite dimensional vector spaces as a matrix transformation, which will allow us to use all of the tools we have developed for matrices to study linear transformations. We will begin with linear transformations from \(\R^n\) to \(\R^m\text{.}\)

Subsection Linear Transformations from \(\R^n\) to \(\R^m\)

Preview Activity 38.1 illustrates the method for representing a linear transformation from \(\R^n\) to \(\R^m\) as a matrix transformation. We now consider the general context.

As we discovered in Activity 38.2, a linear transformation from \(\R^n\) to \(\R^m\) can be expressed as a matrix transformation where the columns of the matrix are given by the images of \(\ve_i\text{,}\) the columns of the \(n\times n\) identity matrix. This matrix is called the standard matrix of the linear transformation.

Subsection The Matrix of a Linear Transformation

We saw in the previous section that any linear transformation \(T\) from \(\R^n\) to \(\R^m\) is in fact a matrix transformation. In this section, we turn to the general question — can any linear transformation \(T: V \to W\) between an \(n\)-dimensional vector space \(V\) and an \(m\)-dimensional vector space \(W\) be represented in some way as a matrix transformation? This will allow us to extend ideas like eigenvalues and eigenvectors to arbitrary linear transformations. We begin by investigating an example.

The general process for representing a linear transformation as a matrix transformation is as described in Activity 38.3.

Activity 38.3 shows us how to represent a linear transformation as a matrix transformation.

If \(V=W\) and \(\CC = \CB\text{,}\) then we use the notation \([T]_{\CB}\) as a shorthand for \([T]_{\CB}^{\CC}\text{.}\) The matrix \([T]_{\CB}^{\CC}\) has the property that

for any \(\vv\) in \(V\text{.}\) Recall that we can find the unique vector in \(W\) whose coordinate vector is \([T(\vv)]_{\CC}\text{,}\) so we have completely realized the transformation \(T\) as a matrix transformation. In essence, we are viewing \(T\) as a composite of linear transformations, first from \(V\) to \(\R^n\text{,}\) then from \(\R^n\) to \(\R^m\text{,}\) then from \(\R^m\) to \(W\) as illustrated in Figure 38.3.

Subsection A Connection between \(\Ker(T)\) and a Matrix Representation of \(T\)

Recall that we defined the kernel of a matrix transformation \(T: \R^n \to \R^m\) to be the set of vectors that \(T\) maps to the zero vector. If \(T\) is the matrix transformation defined by \(T(\vx) = A \vx\text{,}\) we also saw that the kernel of \(T\) is the same as the null space of \(A\text{.}\) We can make a similar connection between a linear transformation and a matrix that defines the transformation.

Activity 38.5 shows that if \(T: V \to W\) is a linear transformation from an \(n\)-dimensional vector space \(V\) with basis \(\CB\) to an \(m\)-dimensional vector space \(W\) with basis \(\CC\text{,}\) then there is a one-to-one correspondence between vectors in \(\Ker(T)\) and vectors in \(\Nul [T]_{\CB}^{\CC}\text{.}\) Recall that \(T\) is one-to-one if and only if \(\Ker(T) = \{\vzero_V\}\text{,}\) where \(\vzero_V\) is the additive identity of \(V\text{.}\) So \(T\) will be one-to-one if and only if \(\Nul [T]_{\CB}^{\CC} = \{\vzero\}\text{.}\) In other words, \(T\) is one-to-one if and only if every column of \(\Nul [T]_{\CB}^{\CC}\) is a pivot column. Note that this does not depend on the basis \(\CB\) and \(\CC\text{.}\)

A similar argument shows that \(T\) is onto if and only if every row of \([T]_{\CB}^{\CC}\) contains a pivot. This is left to the exercises (see Exercise 7).

Subsection Examples

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

Subsection Summary

• The standard matrix for a linear transformation \(T\) from \(\R^n\) to \(\R^m\) is the matrix

  \begin{equation*} A = [T(\ve_1) \ T(\ve_2) \ \cdots \ T(\ve_n)]\text{,} \end{equation*}

  where \(\{\ve_1, \ve_2, \ldots, \ve_n\}\) is the standard basis for \(\R^n\text{.}\) Then \(T\) is the matrix transformation defined by \(T(\vx) = A\vx\) for all \(\vx\) in \(\R^n\text{.}\)

• Let \(V\) be an \(n\) dimensional vector space and \(W\) an \(m\) dimensional vector space and suppose \(T : V \to W\) is a linear transformation. Let \(\CB = \{\vv_1, \vv_2, \ldots, \vv_n\}\) be a basis for \(V\) and \(\CC = \{\vw_1, \vw_2, \ldots, \vw_m\}\) a basis for \(W\text{.}\) The matrix for \(T\) with respect to the bases \(\CB\) and \(\CC\) is the matrix

  \begin{equation*} [T]_{\CB}^{\CC} = \left[ [T(\vv_1)]_{\CC} \ [T(\vv_2)]_{\CC} \ [T(\vv_3)]_{\CC} \ \cdots \ [T(\vv_n)]_{\CC} \right]\text{.} \end{equation*}

  If \(V=W\) and \(\CC = \CB\text{,}\) then we use the notation \([T]_{\CB}\) as a shorthand for \([T]_{\CB}^{\CC}\text{.}\) The matrix \([T]_{\CB}^{\CC}\) has the property that

  \begin{equation*} [T(\vv)]_{\CC} = [T]_{\CB}^{\CC} [\vv]_{\CB} \end{equation*}

  for any \(\vv\) in \(V\text{.}\)

• The matrix for a linear transformation allows us to represent any linear transformation between finite dimensional vectors spaces as a matrix transformation. When we view a linear transformation \(T\) as a matrix transformation, we are able to use the matrix tools we have developed to understand \(T\text{.}\)

Subsection Project: Shamir's Secret Sharing and Lagrange Polynomials

Shamir's Secret Sharing is a secret sharing algorithm developed by the Israeli cryptographer Adi Shamir, who also contributed to the invention of RSA algorithm. The idea is to develop shares related to a secret code that can be distributed in such a way that the secret code can only be discovered if a fixed number of shareholders combine their information.

The general algorithm for Shamir's Secret Sharing works by creating a polynomial with the secret code as one coefficient and random remaining coefficients. More specifically, to create a \((k,n)\) threshold scheme, let \(a_0\) be the secret code. Then choose at random \(k-1\) positive integers \(a_1\text{,}\) \(a_2\text{,}\) \(\ldots\text{,}\) \(a_{k-1}\) and create the polynomial

where \(a_0\) is the secret. Evaluate \(p(t)\) at \(n\) different inputs \(t_1\text{,}\) \(t_2\text{,}\) \(\ldots\text{,}\) \(t_n\) to create \(n\) points \(P_1 = (t_1,p(t_1))\text{,}\) \(P_2 = (t_2,p(t_2))\text{,}\) \(\ldots\text{,}\) \(P_n = (t_n, p(t_n))\text{.}\) Each participant is given one of these points. Since any collection of \(k\) distinct points on the graph of \(p(t)\) uniquely determines \(p(t)\text{,}\) any combination of \(k\) of the participants could reconstruct \(p(t)\text{.}\) The secret is then \(p(0)\text{.}\) (Note that, except under very restrictive circumstances, there is no polynomial of degree less than \(k\) that passes through the given \(k\) points, so it would be impossible for fewer than \(k\) participants to reconstruct the message.)

As an example, let our secret code be \(a_0=1234\text{.}\) Let \(n = 6\) and \(k = 3\text{.}\) Choose two positive integers at random, say \(a_1 = 100\) and \(a_2 = 38\text{.}\) Then

Now we construct \(6\) points by selecting \(6\) positive integers, say \(t_1 = 1\text{,}\) \(t_2 = 2\text{,}\) \(t_3 = 3\text{,}\) \(t_4 = 4\text{,}\) \(t_5 = 5\text{,}\) and \(t_6 = 6\text{.}\) Evaluating \(p(t)\) at \(t=1\) through \(t=6\) gives us the points \(P_1 = (1,1372)\text{,}\) \(P_2 = (2,1586)\text{,}\) \(P_3 = (3,1876)\text{,}\) \(P_4 = (4,2242)\text{,}\) \(P_5 = (5,2684)\text{,}\) and \(P_6 = (6,3202)\text{.}\) Our goal is to find the polynomial that passes through any three of these points. The next activity will show us how to find this polynomial.

The polynomials \(\ell_1(t)\text{,}\) \(\ell_2(t)\text{,}\) and \(\ell_3(t)\) in Project Activity 38.6 are examples of Lagrange polynomials. Project Activity 38.6 shows that fitting polynomials to given points can be accomplished easily using linear combinations of Lagrange polynomials. Now we want to better understand the general formulas for the Lagrange polynomials \(\ell_i(t)\text{.}\)

Now we return to our secret code with \(a_0 = 1234\text{.}\)

The Shamir Secret Sharing algorithm depends on being able to find a unique polynomial \(p(t)\) that passes through the created points. We can understand this result with Lagrange polynomials.