text:
Linear Algebra/Inverses

We now consider how to represent the inverse of a linear map.

We start by recalling some facts about function inverses. Some functions have no inverse, or have an inverse on the left side or right side only.

(An example of a function with no inverse on either side is the zero transformation on $$\mathbb{R}^2$$.) Some functions have a two-sided inverse map, another function that is the inverse of the first, both from the left and from the right. For instance, the map given by $$\vec{v}\mapsto 2\cdot \vec{v}$$ has the two-sided inverse $$\vec{v}\mapsto (1/2)\cdot\vec{v}$$. In this subsection we will focus on two-sided inverses. The appendix shows that a function has a two-sided inverse if and only if it is both one-to-one and onto. The appendix also shows that if a function $$f$$ has a two-sided inverse then it is unique, and so it is called "the" inverse, and is denoted $$f^{-1}$$. So our purpose in this subsection is, where a linear map $$h$$ has an inverse, to find the relationship between $${\rm Rep}_{B,D}(h)$$ and $${\rm Rep}_{D,B}(h^{-1})$$ (recall that we have shown, in Theorem II.2.21 of Section II of this chapter, that if a linear map has an inverse then the inverse is a linear map also).

Because of the correspondence between linear maps and matrices, statements about map inverses translate into statements about matrix inverses.

Here is the arrow diagram giving the relationship between map inverses and matrix inverses. It is a special case of the diagram for function composition and matrix multiplication.

Beyond its place in our general program of seeing how to represent map operations, another reason for our interest in inverses comes from solving linear systems. A linear system is equivalent to a matrix equation, as here.

\begin{array}{*{2}{rc}r} x_1 &+  &x_2  &=  &3  \\ 2x_1 &-  &x_2  &=  &2 \end{array} \quad\Longleftrightarrow\quad \begin{pmatrix} 1 &1  \\ 2  &-1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} 3 \\ 2 \end{pmatrix} \qquad\qquad (*)$$

By fixing spaces and bases (e.g., $$\mathbb{R}^2,\mathbb{R}^2$$ and $$\mathcal{E}_2,\mathcal{E}_2$$), we take the matrix $$H$$ to represent some map $$h$$. Then solving the system is the same as asking: what domain vector $$\vec{x}$$ is mapped by $$h$$ to the result $$\vec{d}\,$$? If we could invert $$h$$ then we could solve the system by multiplying $${\rm Rep}_{D,B}(h^{-1})\cdot{\rm Rep}_{D}(\vec{d})$$ to get $${\rm Rep}_{B}(\vec{x})$$.

We finish by describing the computational procedure usually used to find the inverse matrix.

This procedure will find the inverse of a general $$n \! \times \! n$$ matrix. The $$2 \! \times \! 2$$ case is handy.

We have seen here, as in the Mechanics of Matrix Multiplication subsection, that we can exploit the correspondence between linear maps and matrices. So we can fruitfully study both maps and matrices, translating back and forth to whichever helps us the most.

Over the entire four subsections of this section we have developed an algebra system for matrices. We can compare it with the familiar algebra system for the real numbers. Here we are working not with numbers but with matrices. We have matrix addition and subtraction operations, and they work in much the same way as the real number operations, except that they only combine same-sized matrices. We also have a matrix multiplication operation and an operation inverse to multiplication. These are somewhat like the familiar real number operations (associativity, and distributivity over addition, for example), but there are differences (failure of commutativity, for example). And, we have scalar multiplication, which is in some ways another extension of real number multiplication. This matrix system provides an example that algebra systems other than the elementary one can be interesting and useful.

Exercises
/Solutions/

title: Linear Algebra/Inverses


text:
Linear Algebra/Changing Representations of Vectors

In converting $${\rm Rep}_{B}(\vec{v})$$ to $${\rm Rep}_{D}(\vec{v})$$ the underlying vector $$\vec{v}$$ doesn't change. Thus, this translation is accomplished by the identity map on the space, described so that the domain space vectors are represented with respect to $$B$$ and the codomain space vectors are represented with respect to $$D$$.

 * [[Image:Linalg_change_basis_arrow.png|x100px]]

(The diagram is vertical to fit with the ones in the next subsection.)

We finish this subsection by recognizing that the change of basis matrices are familiar.

In the next subsection we will see how to translate among representations of maps, that is, how to change $${\rm Rep}_{B,D}(h)$$ to $${\rm Rep}_{\hat{B},\hat{D}}(h)$$. The above corollary is a special case of this, where the domain and range are the same space, and where the map is the identity map.

Exercises
/Solutions/

license: Creative Commons - Attribution Share-Alike - https://creativecommons.org/licenses/by-sa/4.0/


text:
Linear Algebra/Changing Map Representations

The first subsection shows how to convert the representation of a vector with respect to one basis to the representation of that same vector with respect to another basis. Here we will see how to convert the representation of a map with respect to one pair of bases to the representation of that map with respect to a different pair. That is, we want the relationship between the matrices in this arrow diagram.

 * [[Image:Linalg_map_change_basis.png|x150px]]

To move from the lower-left of this diagram to the lower-right we can either go straight over, or else up to $$V_B$$ then over to $$W_D$$ and then down. Restated in terms of the matrices, we can calculate $$\hat{H}={\rm Rep}_{\hat{B},\hat{D}}(h)$$ either by simply using $$\hat{B}$$ and $$\hat{D}$$, or else by first changing bases with $${\rm Rep}_{\hat{B},B}(\mbox{id})$$ then multiplying by $$ H={\rm Rep}_{B,D}(h) $$ and then changing bases with $${\rm Rep}_{D,\hat{D}}(\mbox{id})$$. This equation summarizes.

\hat{H}= {\rm Rep}_{D,\hat{D}}(\mbox{id})\cdot H\cdot {\rm Rep}_{\hat{B},B}(\mbox{id}) \qquad\qquad(*)$$

(To compare this equation with the sentence before it, remember that the equation is read from right to left because function composition is read right to left and matrix multiplication represent the composition.)

Naturally, we usually prefer basis changes that make the representation easier to understand. When the representation with respect to equal starting and ending bases is a diagonal matrix we say the map or matrix has been diagonalized. In Chaper Five we shall see which maps and matrices are diagonalizable, and where one is not, we shall see how to get a representation that is nearly diagonal.

We finish this subsection by considering the easier case where representations are with respect to possibly different starting and ending bases. Recall that the prior subsection shows that a matrix changes bases if and only if it is nonsingular. That gives us another version of the above arrow diagram and equation ($$*$$).

Problem 10 checks that matrix equivalence is an equivalence relation. Thus it partitions the set of matrices into matrix equivalence classes.

We can get some insight into the classes by comparing matrix equivalence with row equivalence (recall that matrices are row equivalent when they can be reduced to each other by row operations). In $$\hat{H}=PHQ$$, the matrices $$P$$ and $$Q$$ are nonsingular and thus each can be written as a product of elementary reduction matrices (see Lemma 4.8 in the previous subsection). Left-multiplication by the reduction matrices making up $$P$$ has the effect of performing row operations. Right-multiplication by the reduction matrices making up $$Q$$ performs column operations. Therefore, matrix equivalence is a generalization of row equivalence— two matrices are row equivalent if one can be converted to the other by a sequence of row reduction steps, while two matrices are matrix equivalent if one can be converted to the other by a sequence of row reduction steps followed by a sequence of column reduction steps.

Thus, if matrices are row equivalent then they are also matrix equivalent (since we can take $$Q$$ to be the identity matrix and so perform no column operations). The converse, however, does not hold.

We will close this section by finding a set of representatives for the matrix equivalence classes.

Sometimes this is described as a block partial-identity form.

\left(\begin{array}{c|c} I &Z  \\  \hline Z  &Z \end{array}\right) $$

In this subsection we have seen how to change the representation of a map with respect to a first pair of bases to one with respect to a second pair. That led to a definition describing when matrices are equivalent in this way. Finally we noted that, with the proper choice of (possibly different) starting and ending bases, any map can be represented in block partial-identity form.

One of the nice things about this representation is that, in some sense, we can completely understand the map when it is expressed in this way: if the bases are $$ B=\langle \vec{\beta}_1,\dots,\vec{\beta}_n \rangle $$ and $$ D=\langle \vec{\delta}_1,\dots,\vec{\delta}_m \rangle $$ then the map sends

c_1\vec{\beta}_1+\dots+c_k\vec{\beta}_k+c_{k+1}\vec{\beta}_{k+1}+\dots +c_n\vec{\beta}_n \;\longmapsto\; c_1\vec{\delta}_1+\dots+c_k\vec{\delta}_k+\vec{0}+\dots+\vec{0} $$

where $$ k $$ is the map's rank. Thus, we can understand any linear map as a kind of projection.

\begin{pmatrix} c_1 \\ \vdots \\ c_k \\ c_{k+1} \\ \vdots \\ c_n \end{pmatrix}_B \;\mapsto\; \begin{pmatrix} c_1 \\ \vdots \\ c_k \\ 0 \\ \vdots \\ 0 \end{pmatrix}_D $$

Of course, "understanding" a map expressed in this way requires that we understand the relationship between $$ B $$ and $$ D $$. However, despite that difficulty, this is a good classification of linear maps. }}

Exercises
/Solutions/


text:
Adventist Youth Honors Answer Book/Insect/Strepsiptera

/Transcluded Modules


text:
Adventist Youth Honors Answer Book/Insect/Raphidioptera

|


text:
Adventist Youth Honors Answer Book/Insect/Megaloptera

|


text:
Linear Algebra/Projection

This section is optional; only the last two sections of Chapter Five require this material.

We have described the projection $$ \pi $$ from $$\mathbb{R}^3$$ into its $$ xy $$ plane subspace as a "shadow map". This shows why, but it also shows that some shadows fall upward. So perhaps a better description is: the projection of $$\vec{v}$$ is the $$\vec{p}$$ in the plane with the property that someone standing on $$\vec{p}$$ and looking straight up or down sees $$\vec{v}$$. In this section we will generalize this to other projections, both orthogonal (i.e., "straight up and down") and nonorthogonal.

title: Linear Algebra/Projection


text:
Linear Algebra/Orthogonal Projection Onto a Line

We first consider orthogonal projection onto a line. To orthogonally project a vector $$ \vec{v} $$ onto a line $$\ell$$, mark the point on the line at which someone standing on that point could see $$ \vec{v} $$ by looking straight up or down (from that person's point of view). The picture shows someone who has walked out on the line until the tip of $$\vec{v}$$ is straight overhead. That is, where the line is described as the span of some nonzero vector $$\ell=\{c\cdot\vec{s}\,\big|\, c\in\mathbb{R}\}$$, the person has walked out to find the coefficient $$c_{\vec{p}}\,$$ with the property that $$\vec{v}-c_{\vec{p}}\cdot\vec{s}\,$$ is orthogonal to $$c_{\vec{p}}\cdot\vec{s}$$. We can solve for this coefficient by noting that because $$\vec{v}-c_{\vec{p}}\vec{s}\,$$ is orthogonal to a scalar multiple of $$\vec{s}\,$$ it must be orthogonal to $$\vec{s}\,$$ itself, and then the consequent fact that the dot product $$(\vec{v}-c_{\vec{p}}\vec{s})\cdot \vec{s}\,$$ is zero gives that $$c_{\vec{p}}=\vec{v}\cdot \vec{s}/\vec{s}\cdot \vec{s}$$.

Problem 13 checks that the outcome of the calculation depends only on the line and not on which vector $$ \vec{s}\, $$ happens to be used to describe that line.

The picture above with the stick figure walking out on the line until $$\vec{v}$$'s tip is overhead is one way to think of the orthogonal projection of a vector onto a line. We finish this subsection with two other ways.

Thus, another way to think of the picture that precedes the definition is that it shows $$\vec{v}$$ as decomposed into two parts, the part with the line (here, the part with the tracks, $$\vec{p}$$), and the part that is orthogonal to the line (shown here lying on the north-south axis). These two are "not interacting" or "independent", in the sense that the east-west car is not at all affected by the north-south part of the wind (see Problem 5). So the orthogonal projection of $$ \vec{v} $$ onto the line spanned by $$ \vec{s}\, $$ can be thought of as the part of $$ \vec{v}\, $$ that lies in the direction of $$ \vec{s} $$.

Finally, another useful way to think of the orthogonal projection is to have the person stand not on the line, but on the vector that is to be projected to the line. This person has a rope over the line and pulls it tight, naturally making the rope orthogonal to the line. That is, we can think of the projection $$ \vec{p}\, $$ as being the vector in the line that is closest to $$ \vec{v} $$ (see Problem 11).

This subsection has developed a natural projection map: orthogonal projection onto a line. As suggested by the examples, it is often called for in applications. The next subsection shows how the definition of orthogonal projection onto a line gives us a way to calculate especially convienent bases for vector spaces, again something that is common in applications. The final subsection completely generalizes projection, orthogonal or not, onto any subspace at all.

Exercises
/Solutions/


text:
Linear Algebra/Gram-Schmidt Orthogonalization

''This subsection is optional. It requires material from the prior, also optional, subsection. The work done here will only be needed in the final two sections of Chapter Five.''

The prior subsection suggests that projecting onto the line spanned by $$ \vec{s} $$ decomposes a vector $$\vec{v}$$ into two parts that are orthogonal and so are "not interacting". We will now develop that suggestion.

Of course, the converse of Corollary 2.3 does not hold— not every basis of every subspace of $$\mathbb{R}^n$$ is made of mutually orthogonal vectors. However, we can get the partial converse that for every subspace of $$\mathbb{R}^n$$ there is at least one basis consisting of mutually orthogonal vectors.

The next result verifies that the process used in those examples works with any basis for any subspace of an $$\mathbb{R}^n$$ (we are restricted to $$\mathbb{R}^n$$ only because we have not given a definition of orthogonality for other vector spaces).

Beyond having the vectors in the basis be orthogonal, we can do more; we can arrange for each vector to have length one by dividing each by its own length (we can normalize the lengths).

Besides its intuitive appeal, and its analogy with the standard basis $$\mathcal{E}_n$$ for $$\mathbb{R}^n$$, an orthonormal basis also simplifies some computations. See Exercise 9, for example.

Exercises
/Solutions/


text:
Linear Algebra/Projection Onto a Subspace

''This subsection, like the others in this section, is optional. It also requires material from the optional earlier subsection on Combining Subspaces.''

The prior subsections project a vector onto a line by decomposing it into two parts: the part in the line $$\mbox{proj}_{[\vec{s}\,]}({\vec{v}\,})$$ and the rest $$\vec{v}-\mbox{proj}_{[\vec{s}\,]}({\vec{v}\,})$$. To generalize projection to arbitrary subspaces, we follow this idea.

This definition doesn't involve a sense of "orthogonal" so we can apply it to spaces other than subspaces of an $$\mathbb{R}^n$$. (Definitions of orthogonality for other spaces are perfectly possible, but we haven't seen any in this book.)

A natural question is: what is the relationship between the projection operation defined above, and the operation of orthogonal projection onto a line? The second picture above suggests the answer— orthogonal projection onto a line is a special case of the projection defined above; it is just projection along a subspace perpendicular to the line. In addition to pointing out that projection along a subspace is a generalization, this scheme shows how to define orthogonal projection onto any subspace of $$\mathbb{R}^n$$, of any dimension.

The two examples that we've seen since Definition 3.4 illustrate the first sentence in that definition. The next result justifies the second sentence.

We can find the orthogonal projection onto a subspace by following the steps of the proof, but the next result gives a convienent formula.

Exercises
/Solutions/


text:
Adventist Youth Honors Answer Book/Insect/Neuroptera

|


text:
Linear Algebra/Topic: Orthonormal Matrices

In The Elements, Euclid considers two figures to be the same if they have the same size and shape. That is, the triangles below are not equal because they are not the same set of points. But they are congruent— essentially indistinguishable for Euclid's purposes— because we can imagine picking the plane up, sliding it over and rotating it a bit, although not warping or stretching it, and then putting it back down, to superimpose the first figure on the second. (Euclid never explicitly states this principle but he uses it often .) In modern terminology, "picking the plane up ..." means considering a map from the plane to itself. Euclid has limited consideration to only certain transformations of the plane, ones that may possibly slide or turn the plane but not bend or stretch it. Accordingly, we define a map $$f:\mathbb{R}^2\to \mathbb{R}^2$$ to be distance-preserving or a rigid motion or an isometry, if for all points $$P_1,P_2\in\mathbb{R}^2$$, the distance from $$f(P_1)$$ to $$f(P_2)$$ equals the distance from $$P_1$$ to $$P_2$$. We also define a plane figure to be a set of points in the plane and we say that two figures are congruent if there is a distance-preserving map from the plane to itself that carries one figure onto the other.

Many statements from Euclidean geometry follow easily from these definitions. Some are: (i) collinearity is invariant under any distance-preserving map (that is, if $$P_1$$, $$P_2$$, and $$P_3$$ are collinear then so are $$f(P_1)$$, $$f(P_2)$$, and $$f(P_3)$$), (ii) betweeness is invariant under any distance-preserving map (if $$P_2$$ is between $$P_1$$ and $$P_3$$ then so is $$f(P_2)$$ between $$f(P_1)$$ and $$f(P_3)$$), (iii) the property of being a triangle is invariant under any distance-preserving map (if a figure is a triangle then the image of that figure is also a triangle), (iv) and the property of being a circle is invariant under any distance-preserving map. In 1872, F. Klein suggested that Euclidean geometry can be characterized as the study of properties that are invariant under these maps. (This forms part of Klein's Erlanger Program, which proposes the organizing principle that each kind of geometry— Euclidean, projective, etc.— can be described as the study of the properties that are invariant under some group of transformations. The word "group" here means more than just "collection", but that lies outside of our scope.)

We can use linear algebra to characterize the distance-preserving maps of the plane.

First, there are distance-preserving transformations of the plane that are not linear. The obvious example is this translation.

\begin{pmatrix} x \\ y \end{pmatrix} \quad\mapsto\quad \begin{pmatrix} x \\ y \end{pmatrix}+\begin{pmatrix} 1 \\ 0 \end{pmatrix}=\begin{pmatrix} x+1 \\ y \end{pmatrix} $$

However, this example turns out to be the only example, in the sense that if $$f$$ is distance-preserving and sends $$\vec{0}$$ to $$\vec{v}_0$$ then the map $$\vec{v}\mapsto f(\vec{v})-\vec{v}_0$$ is linear. That will follow immediately from this statement: a map $$t$$ that is distance-preserving and sends $$\vec{0}$$ to itself is linear. To prove this equivalent statement, let

t(\vec{e}_1)=\begin{pmatrix} a \\ b \end{pmatrix} \qquad t(\vec{e}_2)=\begin{pmatrix} c \\ d \end{pmatrix} $$

for some $$a,b,c,d\in\mathbb{R}$$. Then to show that $$t$$ is linear, we can show that it can be represented by a matrix, that is, that $$t$$ acts in this way for all $$x,y\in\mathbb{R}$$.

\vec{v}=\begin{pmatrix} x \\  y \end{pmatrix} \stackrel{t}{\longmapsto} \begin{pmatrix} ax+cy \\  bx+dy \end{pmatrix} \qquad\qquad(*)$$

Recall that if we fix three non-collinear points then any point in the plane can be described by giving its distance from those three. So any point $$\vec{v}$$ in the domain is determined by its distance from the three fixed points $$\vec{0}$$, $$\vec{e}_1$$, and $$\vec{e}_2$$. Similarly, any point $$t(\vec{v})$$ in the codomain is determined by its distance from the three fixed points $$t(\vec{0})$$, $$t(\vec{e}_1)$$, and $$t(\vec{e}_2)$$ (these three are not collinear because, as mentioned above, collinearity is invariant and $$\vec{0}$$, $$\vec{e}_1$$, and $$\vec{e}_2$$ are not collinear). In fact, because $$t$$ is distance-preserving, we can say more: for the point $$\vec{v}$$ in the plane that is determined by being the distance $$d_0$$ from $$\vec{0}$$, the distance $$d_1$$ from $$\vec{e}_1$$, and the distance $$d_2$$ from $$\vec{e}_2$$, its image $$t(\vec{v})$$ must be the unique point in the codomain that is determined by being $$d_0$$ from $$t(\vec{0})$$, $$d_1$$ from $$t(\vec{e}_1)$$, and $$d_2$$ from $$t(\vec{e}_2)$$. Because of the uniqueness, checking that the action in ($$*$$) works in the $$d_0$$, $$d_1$$, and $$d_2$$ cases

\text{dist}\,(\begin{pmatrix} x \\ y \end{pmatrix},\vec{0}) =\text{dist}\,(t(\begin{pmatrix} x \\ y \end{pmatrix}),t(\vec{0})) =\text{dist}\,(\begin{pmatrix} ax+cy \\ bx+dy \end{pmatrix},\vec{0}) $$

($$t$$ is assumed to send $$\vec{0}$$ to itself)

\text{dist}\,(\begin{pmatrix} x \\ y \end{pmatrix},\vec{e}_1) =\text{dist}\,(t(\begin{pmatrix} x \\ y \end{pmatrix}),t(\vec{e}_1)) =\text{dist}\,(\begin{pmatrix} ax+cy \\ bx+dy \end{pmatrix},\begin{pmatrix} a \\ b \end{pmatrix}) $$

and

\text{dist}\,(\begin{pmatrix} x \\ y \end{pmatrix},\vec{e}_2) =\text{dist}\,(t(\begin{pmatrix} x \\ y \end{pmatrix}),t(\vec{e}_2)) =\text{dist}\,(\begin{pmatrix} ax+cy \\ bx+dy \end{pmatrix},\begin{pmatrix} c \\ d \end{pmatrix}) $$

suffices to show that ($$*$$) describes $$t$$. Those checks are routine.

Thus, any distance-preserving $$f:\mathbb{R}^2\to \mathbb{R}^2$$ can be written $$f(\vec{v})=t(\vec{v})+\vec{v}_0$$ for some constant vector $$\vec{v}_0$$ and linear map $$t$$ that is distance-preserving.

Not every linear map is distance-preserving, for example, $$\vec{v}\mapsto 2\vec{v}$$ does not preserve distances. But there is a neat characterization: a linear transformation $$t$$ of the plane is distance-preserving if and only if both $$|t(\vec{e}_1)|=|t(\vec{e}_2)|=1$$ and $$t(\vec{e}_1)$$ is orthogonal to $$t(\vec{e}_2)$$. The "only if" half of that statement is easy— because $$t$$ is distance-preserving it must preserve the lengths of vectors, and because $$t$$ is distance-preserving the Pythagorean theorem shows that it must preserve orthogonality. For the "if" half, it suffices to check that the map preserves lengths of vectors, because then for all $$\vec{p}$$ and $$\vec{q}$$ the distance between the two is preserved $$|t(\vec{p}-\vec{q}\,)|=|t(\vec{p})-t(\vec{q}\,)| =|\vec{p}-\vec{q}\,|$$. For that check, let

\vec{v}=\begin{pmatrix} x \\ y \end{pmatrix} \quad t(\vec{e}_1)=\begin{pmatrix} a \\ b \end{pmatrix} \quad t(\vec{e}_2)=\begin{pmatrix} c \\ d \end{pmatrix} $$

and, with the "if" assumptions that $$a^2+b^2=c^2+d^2=1$$ and $$ac+bd=0$$ we have this.

 * $$\begin{array}{rl}

&= (ax+cy)^2+(bx+dy)^2 \\ &= a^2x^2+2acxy+c^2y^2+b^2x^2+2bdxy+d^2y^2 \\ &= x^2(a^2+b^2)+y^2(c^2+d^2)+2xy(ac+bd) \\ &= x^2 + y^2 \\ &= |\vec{v}\,|^2 \end{array}$$
 * t(\vec{v}\,)|^2

One thing that is neat about this characterization is that we can easily recognize matrices that represent such a map with respect to the standard bases. Those matrices have that when the columns are written as vectors then they are of length one and are mutually orthogonal. Such a matrix is called an orthonormal matrix or orthogonal matrix (the first term is commonly used to mean not just that the columns are orthogonal, but also that they have length one).

We can use this insight to delimit the geometric actions possible in distance-preserving maps. Because $$|t(\vec{v}\,)|=|\vec{v}\,|$$, any $$\vec{v}$$ is mapped by $$t$$ to lie somewhere on the circle about the origin that has radius equal to the length of $$\vec{v}$$. In particular, $$\vec{e}_1$$ and $$\vec{e}_2$$ are mapped to the unit circle. What's more, once we fix the unit vector $$\vec{e}_1$$ as mapped to the vector with components $$a$$ and $$b$$ then there are only two places where $$\vec{e}_2$$ can be mapped if that image is to be perpendicular to the first vector: one where $$\vec{e}_2$$ maintains its position a quarter circle clockwise from $$\vec{e}_1$$ $${\rm Rep}_{\mathcal{E}_2,\mathcal{E}_2}(t)= \begin{pmatrix} a &-b  \\ b &a \end{pmatrix}$$ and one where is is mapped a quarter circle counterclockwise. $${\rm Rep}_{\mathcal{E}_2,\mathcal{E}_2}(t)= \begin{pmatrix} a &b  \\ b &-a \end{pmatrix}$$

We can geometrically describe these two cases. Let $$\theta$$ be the angle between the $$x$$-axis and the image of $$\vec{e}_1$$, measured counterclockwise. The first matrix above represents, with respect to the standard bases, a rotation of the plane by $$\theta$$ radians. $$\begin{pmatrix} x \\ y \end{pmatrix} \stackrel{t}{\longmapsto} \begin{pmatrix} x\cos\theta-y\sin\theta \\ x\sin\theta+y\cos\theta \end{pmatrix}$$ The second matrix above represents a reflection of the plane through the line bisecting the angle between $$\vec{e}_1$$ and $$t(\vec{e}_1)$$. $$\begin{pmatrix} x \\ y \end{pmatrix}\stackrel{t}{\longmapsto} \begin{pmatrix} x\cos\theta+y\sin\theta \\  x\sin\theta-y\cos\theta \end{pmatrix}$$ (This picture shows $$\vec{e}_1$$ reflected up into the first quadrant and $$\vec{e}_2$$ reflected down into the fourth quadrant.)

Note again: the angle between $$\vec{e}_1$$ and $$\vec{e}_2$$ runs counterclockwise, and in the first map above the angle from $$t(\vec{e}_1)$$ to $$t(\vec{e}_2)$$ is also counterclockwise, so the orientation of the angle is preserved. But in the second map the orientation is reversed. A distance-preserving map is direct if it preserves orientations and opposite if it reverses orientation.

So, we have characterized the Euclidean study of congruence: it considers, for plane figures, the properties that are invariant under combinations of (i) a rotation followed by a translation, or (ii) a reflection followed by a translation (a reflection followed by a non-trivial translation is a glide reflection).

Another idea, besides congruence of figures, encountered in elementary geometry is that figures are similar if they are congruent after a change of scale. These two triangles are similar since the second is the same shape as the first, but $$3/2$$-ths the size. From the above work, we have that figures are similar if there is an orthonormal matrix $$T$$ such that the points $$\vec{q}$$ on one are derived from the points $$\vec{p}$$ by $$\vec{q}=(kT)\vec{v}+\vec{p}_0$$ for some nonzero real number $$k$$ and constant vector $$\vec{p}_0$$.

Although many of these ideas were first explored by Euclid, mathematics is timeless and they are very much in use today. One application of the maps studied above is in computer graphics. We can, for example, animate this top view of a cube by putting together film frames of it rotating; that's a rigid motion. We could also make the cube appear to be moving away from us by producing film frames of it shrinking, which gives us figures that are similar. Computer graphics incorporates techniques from linear algebra in many other ways (see Problem 4).

So the analysis above of distance-preserving maps is useful as well as interesting. A beautiful book that explores some of this area is. More on groups, of transformations and otherwise, can be found in any book on Modern Algebra, for instance. More on Klein and the Erlanger Program is in.

Exercises
/Solutions/


text:
Linear Algebra/Topic: Geometry of Linear Maps

The pictures below contrast $$ f_1(x)=e^x $$ and $$ f_2(x)=x^2 $$, which are nonlinear, with $$ h_1(x)=2x $$ and $$ h_2(x)=-x $$, which are linear. Each of the four pictures shows the domain $$\mathbb{R}^1$$ on the left mapped to the codomain $$\mathbb{R}^1$$ on the right. Arrows trace out where each map sends $$x=0$$, $$x=1$$, $$x=2$$, $$x=-1$$, and $$x=-2$$. Note how the nonlinear maps distort the domain in transforming it into the range. For instance, $$ f_1(1) $$ is further from $$f_1(2)$$ than it is from $$f_1(0)$$ — the map is spreading the domain out unevenly so that an interval near $$x=2$$ is spread apart more than is an interval near $$x=0$$ when they are carried over to the range. The linear maps are nicer, more regular, in that for each map all of the domain is spread by the same factor.

The only linear maps from $$\mathbb{R}^1$$ to $$\mathbb{R}^1$$ are multiplications by a scalar. In higher dimensions more can happen. For instance, this linear transformation of $$\mathbb{R}^2$$, rotates vectors counterclockwise, and is not just a scalar multiplication. The transformation of $$\mathbb{R}^3$$ which projects vectors into the $$xz$$-plane is also not just a rescaling. Nonetheless, even in higher dimensions the situation isn't too complicated.

Below, we use the standard bases to represent each linear map $$h:\mathbb{R}^n\to \mathbb{R}^m$$ by a matrix $$H$$. Recall that any $$H$$ can be factored $$H=PBQ$$, where $$P$$ and $$Q$$ are nonsingular and $$B$$ is a partial-identity matrix. Further, recall that nonsingular matrices factor into elementary matrices $$PBQ=T_nT_{n-1}\cdots T_jBT_{j-1}\cdots T_1$$, which are matrices that are obtained from the identity $$I$$ with one Gaussian step

I\xrightarrow[]{k\rho_i}M_i(k) \qquad I\xrightarrow[]{\rho_i\leftrightarrow\rho_j}P_{i,j} \qquad I\xrightarrow[]{k\rho_i+\rho_j}C_{i,j}(k) $$

($$i\neq j$$, $$k\neq 0$$). So if we understand the effect of a linear map described by a partial-identity matrix, and the effect of linear mapss described by the elementary matrices, then we will in some sense understand the effect of any linear map. (The pictures below stick to transformations of $$\mathbb{R}^2$$ for ease of drawing, but the statements hold for maps from any $$\mathbb{R}^n$$ to any $$\mathbb{R}^m$$.)

The geometric effect of the linear transformation represented by a partial-identity matrix is projection.

\begin{pmatrix} x \\ y \\ z \end{pmatrix} \quad\xrightarrow{\begin{pmatrix} 1 &0  &0   \\ 0  &1  &0   \\ 0  &0  &0   \end{pmatrix}_{\mathcal{E}_3,\mathcal{E}_3}}\quad \begin{pmatrix} x \\ y \\ 0 \end{pmatrix} $$

For the $$M_i(k)$$ matrices, the geometric action of a transformation represented by such a matrix (with respect to the standard basis) is to  stretch vectors by a factor of $$k$$ along the $$i$$-th axis. This map stretches by a factor of $$3$$ along the $$x$$-axis. Note that if $$0\leq k<1$$ or if $$k<0$$ then the $$i$$-th component goes the other way; here, toward the left. Either of these is a dilation.

The action of a transformation represented by a $$P_{i,j}$$ permutation matrix is to interchange the $$i$$-th and $$j$$-th axes; this is a particular kind of reflection. In higher dimensions, permutations involving many axes can be decomposed into a combination of swaps of pairs of axes— see Problem 5.

The remaining case is that of matrices of the form $$C_{i,j}(k)$$. Recall that, for instance, that $$C_{1,2}(2)$$ performs $$2\rho_1+\rho_2$$.

\begin{pmatrix} x \\  y \end{pmatrix} \xrightarrow{\begin{pmatrix} 1 &0  \\ 2  &1  \end{pmatrix}_{\mathcal{E}_2,\mathcal{E}_2}} \qquad \begin{pmatrix} x \\ 2x+y \end{pmatrix} $$

In the picture below, the vector $$\vec{u}$$ with the first component of $$1$$ is affected less than the vector $$\vec{v}$$ with the first component of $$2$$— $$h(\vec{u})$$ is only $$2$$ higher than $$\vec{u}$$ while $$h(\vec{v})$$ is $$4$$ higher than $$\vec{v}$$. Any vector with a first component of $$1$$ would be affected as is $$\vec{u}$$; it would be slid up by $$2$$. And any vector with a first component of $$2$$ would be slid up $$4$$, as was $$\vec{v}$$. That is, the transformation represented by $$C_{i,j}(k)$$ affects vectors depending on their $$i$$-th component.

Another way to see this same point is to consider the action of this map on the unit square. In the next picture, vectors with a first component of $$0$$, like the origin, are not pushed vertically at all but vectors with a positive first component are slid up. Here, all vectors with a first component of $$1$$— the entire right side of the square— is affected to the same extent. More generally, vectors on the same vertical line are slid up the same amount, namely, they are slid up by twice their first component. The resulting shape, a rhombus, has the same base and height as the square (and thus the same area) but the right angles are gone. For contrast the next picture shows the effect of the map represented by $$C_{2,1}(1)$$. In this case, vectors are affected according to their second component. The vector $$\binom{x}{y}$$ is slid horozontally by twice $$y$$.

Because of this action, this kind of map is called a shear.

With that, we have covered the geometric effect of the four types of components in the expansion $$H=T_nT_{n-1}\cdots T_jBT_{j-1}\cdots T_1$$, the partial-identity projection $$B$$ and the elementary $$T_i$$'s. Since we understand its components, we in some sense understand the action of any $$H$$. As an illustration of this assertion, recall that under a linear map, the image of a subspace is a subspace and thus the linear transformation $$h$$ represented by $$H$$ maps lines through the origin to lines through the origin. (The dimension of the image space cannot be greater than the dimension of the domain space, so a line can't map onto, say, a plane.) We will extend that to show that any line, not just those through the origin, is mapped by $$h$$ to a line. The proof is simply that the partial-identity projection $$B$$ and the elementary $$T_i$$'s each turn a line input into a line output (verifying the four cases is Problem 6), and therefore their composition also preserves lines. Thus, by understanding its components we can understand arbitrary square matrices $$H$$, in the sense that we can prove things about them.

An understanding of the geometric effect of linear transformations on $$\mathbb{R}^n$$ is very important in mathematics. Here is a familiar application from calculus. On the left is a picture of the action of the nonlinear function $$ y(x)=x^2+x $$. As at that start of this Topic, overall the geometric effect of this map is irregular in that at different domain points it has different effects (e.g., as the domain point $$x$$ goes from $$2$$ to $$-2$$, the associated range point $$f(x)$$ at first decreases, then pauses instantaneously, and then increases). But in calculus we don't focus on the map overall, we focus instead on the local effect of the map.

At $$x=1$$ the derivative is $$ y^\prime(1)=3 $$, so that near $$ x=1 $$ we have $$ \Delta y\approx 3\cdot\Delta x $$.

That is, in a neighborhood of $$x=1$$, in carrying the domain to the codomain this map causes it to grow by a factor of $$3$$ — it is, locally, approximately, a dilation.

The picture below shows a small interval in the domain $$(x-\Delta x\,..\,x+\Delta x)$$ carried over to an interval in the codomain $$(y-\Delta y\,..\,y+\Delta y)$$ that is three times as wide: $$\Delta y \approx 3\cdot \Delta x$$. (When the above picture is drawn in the traditional cartesian way then the prior sentence about the rate of growth of $$y(x)$$ is usually stated: the derivative $$y^\prime(1)=3$$ gives the slope of the line tangent to the graph at the point $$(1,2)$$.)

In higher dimensions, the idea is the same but the approximation is not just the $$\mathbb{R}^1$$-to-$$\mathbb{R}^1$$ scalar multiplication case. Instead, for a function $$ y:\mathbb{R}^n\to \mathbb{R}^m $$ and a point $$ \vec{x}\in\mathbb{R}^n $$, the derivative is defined to be the linear map $$ h:\mathbb{R}^n\to \mathbb{R}^m $$ best approximating how $$ y $$ changes near $$ y(\vec{x}) $$. So the geometry studied above applies.

We will close this Topic by remarking how this point of view makes clear an often-misunderstood, but very important, result about derivatives: the derivative of the composition of two functions is computed by using the Chain Rule for combining their derivatives. Recall that (with suitable conditions on the two functions)

\frac{d\,(g\circ f)}{dx}(x) = \frac{dg}{dx}(f(x))\cdot\frac{df}{dx}(x) $$

so that, for instance, the derivative of $$\sin(x^2+3x)$$ is $$\cos(x^2+3x)\cdot(2x+3)$$. How does this combination arise? From this picture of the action of the composition. The first map $$f$$ dilates the neighborhood of $$x$$ by a factor of

\frac{df}{dx}(x) $$

and the second map $$g$$ dilates some more, this time dilating a neighborhood of $$f(x)$$ by a factor of

\frac{dg}{dx}(\,f(x)\,) $$

and as a result, the composition dilates by the product of these two.

In higher dimensions the map expressing how a function changes near a point is a linear map, and is expressed as a matrix. (So we understand the basic geometry of higher-dimensional derivatives; they are compositions of dilations, interchanges of axes, shears, and a projection). And, the Chain Rule just multiplies the matrices.

Thus, the geometry of linear maps $$h:\mathbb{R}^n\to \mathbb{R}^m$$ is appealing both for its simplicity and for its usefulness.

Exercises
/Solutions/


text:
Linear Algebra/Topic: Markov Chains

Here is a simple game: a player bets on coin tosses, a dollar each time, and the game ends either when the player has no money left or is up to five dollars. If the player starts with three dollars, what is the chance that the game takes at least five flips? Twenty-five flips?

At any point, this player has either $0, or $1, ..., or $5. We say that the player is in the state $$s_0$$, $$s_1$$, ..., or $$s_5$$. A game consists of moving from state to state. For instance, a player now in state $$s_3$$ has on the next flip a $$0.5$$ chance of moving to state $$s_2$$ and a $$0.5$$ chance of moving to $$s_4$$. The boundary states are a bit different; once in state $$s_0$$ or stat $$s_5$$, the player never leaves.

Let $$p_{i}(n)$$ be the probability that the player is in state $$s_i$$ after $$n$$ flips. Then, for instance, we have that the probability of being in state $$s_0$$ after flip $$n+1$$ is $$p_{0}(n+1)=p_{0}(n)+0.5\cdot p_{1}(n)$$. This matrix equation summarizes.

\begin{pmatrix} 1 &0.5 &0   &0   &0    &0  \\ 0.5  &0   &0.5 &0   &0    &0  \\ 0  &0.5 &0   &0.5 &0    &0  \\ 0  &0   &0.5 &0   &0.5  &0  \\ 0  &0   &0   &0.5 &0    &0.5  \\ 0  &0   &0   &0   &0.5  &1   \end{pmatrix} \begin{pmatrix} p_{0}(n) \\ p_{1}(n) \\ p_{2}(n) \\ p_{3}(n) \\ p_{4}(n) \\ p_{5}(n) \end{pmatrix} =\begin{pmatrix} p_{0}(n+1) \\ p_{1}(n+1) \\ p_{2}(n+1) \\ p_{3}(n+1) \\ p_{4}(n+1) \\ p_{5}(n+1) \end{pmatrix} $$

With the initial condition that the player starts with three dollars, calculation gives this. As this computational exploration suggests, the game is not likely to go on for long, with the player quickly ending in either state $$s_0$$ or state $$s_5$$. For instance, after the fourth flip there is a probability of $$0.50$$ that the game is already over. (Because a player who enters either of the boundary states never leaves, they are said to be absorbing.)

This game is an example of a Markov chain, named for A.A. Markov, who worked in the first half of the 1900's. Each vector of $$p$$'s is a probability vector and the matrix is a transition matrix. The notable feature of a Markov chain model is that it is historyless in that with a fixed transition matrix, the next state depends only on the current state, not on any prior states. Thus a player, say, who arrives at $$s_2$$ by starting in state $$s_3$$, then going to state $$s_2$$, then to $$s_1$$, and then to $$s_2$$ has at this point exactly the same chance of moving next to state $$s_3$$ as does a player whose history was to start in $$s_3$$, then go to $$s_4$$, and to $$s_3$$, and then to $$s_2$$.

Here is a Markov chain from sociology. A study divided occupations in the United Kingdom into upper level (executives and professionals), middle level (supervisors and skilled manual workers), and lower level (unskilled). To determine the mobility across these levels in a generation, about two thousand men were asked, "At which level are you, and at which level was your father when you were fourteen years old?" This equation summarizes the results.

\begin{pmatrix} 0.60 & 0.29  & 0.16  \\ 0.26  & 0.37  & 0.27  \\ 0.14  & 0.34  & 0.57  \end{pmatrix} \begin{pmatrix} p_{U}(n) \\ p_{M}(n) \\ p_{L}(n) \end{pmatrix} =\begin{pmatrix} p_{U}(n+1) \\ p_{M}(n+1) \\ p_{L}(n+1) \end{pmatrix} $$

For instance, a child of a lower class worker has a $$.27$$ probability of growing up to be middle class. Notice that the Markov model assumption about history seems reasonable— we expect that while a parent's occupation has a direct influence on the occupation of the child, the grandparent's occupation has no such direct influence. With the initial distribution of the respondents's fathers given below, this table lists the distributions for the next five generations.

One more example, from a very important subject, indeed. The World Series of American baseball is played between the team winning the American League and the team winning the National League (we follow [Brunner] but see also [Woodside]). The series is won by the first team to win four games. That means that a series is in one of twenty-four states: 0-0 (no games won yet by either team), 1-0 (one game won for the American League team and no games for the National League team), etc. If we assume that there is a probability $$p$$ that the American League team wins each game then we have the following transition matrix.

\begin{pmatrix} 0     &0      &0      &0   &\ldots  \\ p     &0      &0      &0   &\ldots  \\ 1-p   &0      &0      &0   &\ldots  \\ 0     &p      &0      &0   &\ldots  \\ 0     &1-p    &p      &0   &\ldots  \\ 0     &0      &1-p    &0   &\ldots  \\ \vdots &\vdots &\vdots &\vdots \end{pmatrix} \begin{pmatrix} p_{\text{0-0}}(n) \\ p_{\text{1-0}}(n) \\ p_{\text{0-1}}(n) \\ p_{\text{2-0}}(n) \\ p_{\text{1-1}}(n) \\ p_{\text{0-2}}(n) \\ \vdots \end{pmatrix} = \begin{pmatrix} p_{\text{0-0}}(n+1) \\ p_{\text{1-0}}(n+1) \\ p_{\text{0-1}}(n+1) \\ p_{\text{2-0}}(n+1) \\ p_{\text{1-1}}(n+1) \\ p_{\text{0-2}}(n+1) \\ \vdots \end{pmatrix} $$

An especially interesting special case is $$p=0.50$$; this table lists the resulting components of the $$n=0$$ through $$n=7$$ vectors. (The code to generate this table in the computer algebra system Octave follows the exercises.) Note that evenly-matched teams are likely to have a long series— there is a probability of $$0.625$$ that the series goes at least six games.

One reason for the inclusion of this Topic is that Markov chains are one of the most widely-used applications of matrix operations. Another reason is that it provides an example of the use of matrices where we do not consider the significance of the maps represented by the matrices. For more on Markov chains, there are many sources such as and.

Exercises
''Use a computer for these problems. You can, for instance, adapt the Octave script given below.''

/Solutions/

 Computer Code

This script markov.m for the computer algebra system Octave was used to generate the table of World Series outcomes. (The sharp character # marks the rest of a line as a comment.)

function w = markov(p,v) q = 1-p; A=[0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0; # 0-0 p,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0; # 1-0 q,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0; # 0-1_ 0,p,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0; # 2-0 0,q,p,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0; # 1-1 0,0,q,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0; # 0-2__ 0,0,0,p,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0; # 3-0 0,0,0,q,p,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0; # 2-1 0,0,0,0,q,p, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0; # 1-2_ 0,0,0,0,0,q, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0; # 0-3 0,0,0,0,0,0, p,0,0,0,1,0, 0,0,0,0,0,0, 0,0,0,0,0,0; # 4-0 0,0,0,0,0,0, q,p,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0; # 3-1__ 0,0,0,0,0,0, 0,q,p,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0; # 2-2 0,0,0,0,0,0, 0,0,q,p,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0; # 1-3 0,0,0,0,0,0, 0,0,0,q,0,0, 0,0,1,0,0,0, 0,0,0,0,0,0; # 0-4_ 0,0,0,0,0,0, 0,0,0,0,0,p, 0,0,0,1,0,0, 0,0,0,0,0,0; # 4-1 0,0,0,0,0,0, 0,0,0,0,0,q, p,0,0,0,0,0, 0,0,0,0,0,0; # 3-2 0,0,0,0,0,0, 0,0,0,0,0,0, q,p,0,0,0,0, 0,0,0,0,0,0; # 2-3__ 0,0,0,0,0,0, 0,0,0,0,0,0, 0,q,0,0,0,0, 1,0,0,0,0,0; # 1-4 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,p,0, 0,1,0,0,0,0; # 4-2 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,q,p, 0,0,0,0,0,0; # 3-3_ 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,q, 0,0,0,1,0,0; # 2-4 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,p,0,1,0; # 4-3 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,0,0,0,0, 0,0,q,0,0,1]; # 3-4 w = A * v; endfunction
 * 1) Octave script file to compute chance of World Series outcomes.

Then the Octave session was this.

> v0=[1;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;0] > p=.5 > v1=markov(p,v0) > v2=markov(p,v1) ...

Translating to another computer algebra system should be easy— all have commands similar to these.

title: Linear Algebra/Topic: Markov Chains


text:
Linear Algebra/Topic: Line of Best Fit

Scientists are often presented with a system that has no solution and they must find an answer anyway. That is, they must find a value that is as close as possible to being an answer.

For instance, suppose that we have a coin to use in flipping. This coin has some proportion $$m$$ of heads to total flips, determined by how it is physically constructed, and we want to know if $$m$$ is near $$1/2$$. We can get experimental data by flipping it many times. This is the result a penny experiment, including some intermediate numbers. Because of randomness, we do not find the exact proportion with this sample — there is no solution to this system.

\begin{array}{*{1}{rc}r} 30m &=  &16    \\ 60m &=  &34    \\ 90m &=  &51 \end{array} $$

That is, the vector of experimental data is not in the subspace of solutions.

\begin{pmatrix} 16 \\ 34 \\ 51 \end{pmatrix}\not\in \{ m\begin{pmatrix} 30 \\ 60 \\ 90 \end{pmatrix} \,\big|\, m\in\mathbb{R}\} $$

However, as described above, we want to find the $$m$$ that most nearly works. An orthogonal projection of the data vector into the line subspace gives our best guess.

\frac{ \begin{pmatrix} 16 \\ 34 \\ 51 \end{pmatrix}\cdot\begin{pmatrix} 30 \\ 60 \\ 90 \end{pmatrix} }{ \begin{pmatrix} 30 \\ 60 \\ 90 \end{pmatrix}\cdot\begin{pmatrix} 30 \\ 60 \\ 90 \end{pmatrix} } \cdot\begin{pmatrix} 30 \\ 60 \\ 90 \end{pmatrix} =\frac{7110}{12600}\cdot \begin{pmatrix} 30 \\ 60 \\ 90 \end{pmatrix} $$

The estimate ($$ m=7110/12600\approx 0.56 $$) is a bit high but not much, so probably the penny is fair enough.

The line with the slope $$ m\approx 0.56 $$ is called the line of best fit for this data. Minimizing the distance between the given vector and the vector used as the right-hand side minimizes the total of these vertical lengths, and consequently we say that the line has been obtained through fitting by least-squares (the vertical scale here has been exaggerated ten times to make the lengths visible).

We arranged the equation above so that the line must pass through $$ (0,0) $$ because we take take it to be (our best guess at) the line whose slope is this coin's true proportion of heads to flips. We can also handle cases where the line need not pass through the origin.

For example, the different denominations of U.S. money have different average times in circulation (the $2 bill is left off as a special case). How long should we expect a $25 bill to last? The plot (see below) looks roughly linear. It isn't a perfect line, i.e., the linear system with equations $$b+1m=1.5$$, ..., $$b+100m=20$$ has no solution, but we can again use orthogonal projection to find a best approximation. Consider the matrix of coefficients of that linear system and also its vector of constants, the experimentally-determined values.

A= \begin{pmatrix} 1 &1  \\    1  &5  \\    1  &10  \\    1  &20  \\    1  &50  \\    1  &100  \end{pmatrix} \qquad \vec{v}=\begin{pmatrix} 1.5 \\ 2 \\ 3 \\ 5 \\ 9 \\ 20 \end{pmatrix} $$

The ending result in the subsection on Projection into a Subspace says that coefficients $$b$$ and $$m$$ so that the linear combination of the columns of $$A$$ is as close as possible to the vector $$\vec{v}$$ are the entries of $$({{A}^{\rm trans}}A)^{-1}{{A}^{\rm trans}}\cdot\vec{v}$$. Some calculation gives an intercept of $$b=1.05$$ and a slope of $$m= 0.18$$. Plugging $$x=25$$ into the equation of the line shows that such a bill should last between five and six years.

We close by considering the times for the men's mile race. These are the world records that were in force on January first of the given years. We want to project when a 3:40 mile will be run. We can see below that the data is surprisingly linear. With this input

A= \begin{pmatrix} 1 & 1860 \\   1 & 1870 \\    \vdots &\vdots  \\ 1 &1990 \\    1 &2000  \end{pmatrix} \qquad \vec{v} = \begin{pmatrix} 280.0 \\ 268.8 \\                   \vdots \\ 226.3 \\                   223.1 \end{pmatrix} $$

the Python program at this Topic's end gives

$$\text{slope}= -0.35$$ and $$\text{intercept}= 925.53$$ (rounded to two places; the original data is good to only about a quarter of a second since much of it was hand-timed). When will a $$ 220 $$ second mile be run? Solving the equation of the line of best fit gives an estimate of the year $$ 2008 $$.

This example is amusing, but serves as a caution — obviously the linearity of the data will break down someday (as indeed it does prior to 1860).

Exercises
''The calculations here are best done on a computer. In addition, some of the problems require more data, available in your library, on the net, in the answers to the exercises, or in the section following the exercises.''

/Solutions/ Computer Code

Additional Data
Data on the progression of the world's records (taken from the Runner's World web site) is below.

title: Linear Algebra/Topic: Line of Best Fit


text:
Talk:Blender 3D: Noob to Pro/Python Platformer: Creation

...I don't know why you're introducing stuff you only need for Blender scripting, but this is all you need to do to move a protagonist around an area, in the BGE. Simplified and commented:

That's (almost) straight from the tutorial I started work on, but if you're going to be covering basic BGE Python, I'll move on the slightly more advanced stuff.

 * FFFffFF I was going to do that!! Oh, and I believe there's an alternate way of registering a key press, but this seems more efficient and/or less likely to make Blender explode. I'll work this code in with an explanation, but I should note which parts you did and which parts I did when I produce the script at the end. Anyway, while yes, you only use this particular code set for Blender scripting, to replicate the conditions we set forth in the other tutorial set, they deal with essential principles of object-oriented game programming. It's showing how one sets up that framework with the Blender-Python affair in particular. My motive for sidetracking the tutorials to Python is that later on I'm going to start introducing AI routines for enemies and such, which will really require Python scripts to be anywhere efficient. Also, it gives me an error if I try to import GameLogic. Why is this? Loki Clock (talk) 01:27, 12 March 2008 (UTC)

 * Well, first of all, I've never had blender explode as a result of this sort of keypress checking, although you are right in saying that there are better ways to do it. Second, with regard to the importing error... What version of Python are you using?  Also, importing GameLogic is not needed, as the game engine automatically does that, but if you don't want to type "GameLogic" every time you need to call a method of it, importing with a shorter name is nice.  So try removing that bit of code and replacing every 'gl' with 'GameLogic'.  And I think a better way to introduce people to OOP and its applications to game programming would be swaroop's section on OOP, perhaps supplemented by some Pygame programming.  There are lots of good OOP introductions out there; why re-invent the wheel?  Especially considering that you can make some pretty decent games with simple procedural programming, there's no good reason to start a set of tutorials with Objkect Oriented Programming.  OOP is generally saved for later, more advanced tutorials.  Anyways, that's my two cents.  What do you think about concentrating more on actually learning GameLogic, rather than going on about Python scripting and OOP?--Malaz (talk) 17:49, 15 March 2008 (UTC)

 * I have 2.5. It doesn't even work when the only line is "import GameLogic". And the tutorials aren't designed to introduce people to OOP, they're designed to tell you the code to set it up in an OOP way. So if someone knows how to build a game with, say, Actionscript, it will teach them how to apply those techniques learned to their Python programming. So when I show how to create a character object linked to a pre-existing mesh, I'm telling the Actionscript people how to do the equivalent of creating an object linked to a graphic. They will understand the point of this because, Python is an OO language and so they are very likely OO programmers, and acts analogous to that are found in most OO game programming situations, anyway. So in a way, it's not a tutorial to teach people OO programming, but more a tutorial for people who ALREADY know it, but that others might be able to see the practicality of, or at least discover said practicality when they realize how much they would have to change to get X to work if Y wasn't given a name to be referred to at the beginning of the series.Loki Clock (talk) 07:41, 18 March 2008 (UTC)

 * Still, I think conventional approaches to learning the Game Engine are easier for people new to the blender API. These tutorials are very much about OOP, but do not teach anything to do with normal pyblender API (ie for mesh scripts).  I feel that this simplifies the learning process, and those interested in conventional Python scripting can take a look at some of the excellent tutorials out there (some of which are in this wikibook).  You are very much right in saying that the OO angle is important to those wishing to make a game (image writing a game using entirely procedural programming!), however I don't think that mesh python is needed to create an elementary game.

 * But if you're going to do that advanced tutorials as well, go ahead. I'll leave this stuff to you, if you think you're doing it the right way, and don't want any help with the normal GameLogic tutorials. --Malaz (talk) 06:11, 23 March 2008 (UTC)

 * By the way, I just made a quick 'proof of concept' for the jump test thing. You can just use a ray sensor; it's much simpler and less of a hack.  I'll upload the .blend somewhere if you want to see it.  It's 144KB, so should be easy to upload somewhere...
 * I could still help with the GameLogic tutorials, but we shouldn't neglect the Python path of things. I'd love to see your jump fix, and I'll probably incorporate it into the official blend for the Platform Fixes tutorial. Loki Clock (talk) 00:10, 30 March 2008 (UTC)
 * And I'm now downloading the special Python 2.5 version, hoping that will fix the gl import problems.
 * It didn't.
 * Okay, according to this thread I can't test GameLogic related affairs with ALT-P, I have to run the normal sim in the 3D view.
 * I'll send the quick jumpTest .blend to you. It'll need some tweaking to make it fully usable within your game, and I would recommend converting it to python to reduce clutter (as I did it in gamelogic to demostrate that it was possible).  Unless you have some hosting, I'll need an e-mail address to send it to.  Also, the majority of the people on that thread are wrong.  There is a GameLogic module, and there is official documentation for it.  Normal GameLogic scripts can be tested by starting the game (PKEY), and looking at the terminal output--make sure to run blender from a terminal (command is blender in linux, depending on your environmental variables).  GameLogic scripting is completely different and seperate from Python scripting, and trying to make a Blender game with the normal Python API is nigh impossible.--Malaz (talk) 00:37, 10 April 2008 (UTC)
 * That will be lokiclock at the place with the gmail and the dot com at the end! Loki Clock (talk) 09:22, 26 April 2008 (UTC)


text:
Linear Algebra/Definition and Examples of Linear Independence

Spanning Sets and Linear Independence
We first characterize when a vector can be removed from a set without changing the span of that set.

The lemma says that if we have a spanning set then we can remove a $$\vec{v}$$ to get a new set $$S$$ with the same span if and only if $$\vec{v}$$ is a linear combination of vectors from $$S$$. Thus, under the second sense described above, a spanning set is minimal if and only if it contains no vectors that are linear combinations of the others in that set. We have a term for this important property.

Here is an important observation:

\vec{s}_0=c_1\vec{s}_1+c_2\vec{s}_2+\cdots +c_n\vec{s}_n $$

although this way of writing one vector as a combination of the others visually sets $$ \vec{s}_0 $$ off from the other vectors, algebraically there is nothing special in that equation about $$ \vec{s}_0 $$. For any $$ \vec{s}_i $$ with a coefficient $$c_i$$ that is nonzero, we can rewrite the relationship to set off $$ \vec{s}_i $$.

\vec{s}_i=(1/c_i)\vec{s}_0+(-c_1/c_i)\vec{s}_1 +\dots+(-c_n/c_i)\vec{s}_n $$

When we don't want to single out any vector by writing it alone on one side of the equation we will instead say that $$\vec{s}_0,\vec{s}_1,\dots,\vec{s}_n $$ are in a linear relationship and write the relationship with all of the vectors on the same side. The next result rephrases the linear independence definition in this style. It gives what is usually the easiest way to compute whether a finite set is dependent or independent.

The above examples, especially Example 1.5, underline the discussion that begins this section. The next result says that given a finite set, we can produce a linearly independent subset by discarding what Remark 1.6 calls "repeats".

Linear Independence and Subset Relations
Theorem 1.12 describes producing a linearly independent set by shrinking, that is, by taking subsets. We finish this subsection by considering how linear independence and dependence, which are properties of sets, interact with the subset relation between sets.

Restated, independence is preserved by subset and dependence is preserved by superset.

Those are two of the four possible cases of interaction that we can consider. The third case, whether linear dependence is preserved by the subset operation, is covered by Example 1.13, which gives a linearly dependent set $$S$$ with a subset $$S_1$$ that is linearly dependent and another subset $$S_2$$ that is linearly independent.

That leaves one case, whether linear independence is preserved by superset. The next example shows what can happen.

So, in general, a linearly independent set may have a superset that is dependent. And, in general, a linearly independent set may have a superset that is independent. We can characterize when the superset is one and when it is the other.

(Compare this result with Lemma 1.1. Both say, roughly, that $$\vec{v}$$ is a "repeat" if it is in the span of $$S$$. However, note the additional hypothesis here of linear independence.)

Lemma 1.16 can be restated in terms of independence instead of dependence: if $$ S $$ is linearly independent and $$ \vec{v}\not\in S $$ then the set $$ S\cup\{\vec{v}\} $$ is also linearly independent if and only if $$ \vec{v}\not\in[S]. $$ Applying Lemma 1.1, we conclude that if $$ S $$ is linearly independent and $$ \vec{v}\not\in S $$ then $$ S\cup\{\vec{v}\} $$ is also linearly independent if and only if $$ [S\cup\{\vec{v}\}]\neq[S] $$. Briefly, when passing from $$S$$ to a superset $$S_1$$, to preserve linear independence we must expand the span $$[S_1]\supset[S]$$.

Example 1.15 shows that some linearly independent sets are maximal— have as many elements as possible— in that they have no supersets that are linearly independent. By the prior paragraph, a linearly independent sets is maximal if and only if it spans the entire space, because then no vector exists that is not already in the span.

This table summarizes the interaction between the properties of independence and dependence and the relations of subset and superset.

In developing this table we've uncovered an intimate relationship between linear independence and span. Complementing the fact that a spanning set is minimal if and only if it is linearly independent, a linearly independent set is maximal if and only if it spans the space.

In summary, we have introduced the definition of linear independence to formalize the idea of the minimality of a spanning set. We have developed some properties of this idea. The most important is Lemma 1.16, which tells us that a linearly independent set is maximal when it spans the space.

Exercises
/Solutions/


text:
Linear Algebra/Definition of Determinant

For $$ 1 \! \times \! 1 $$ matrices, determining nonsingularity is trivial. $$ \begin{pmatrix} a \end{pmatrix} $$ is nonsingular iff $$ a \neq 0 $$ The $$2 \! \times \! 2$$ formula came out in the course of developing the inverse. $$ \begin{pmatrix} a &b  \\ c &d \end{pmatrix} $$ is nonsingular iff $$ ad-bc \neq 0 $$ The $$3 \! \times \! 3$$ formula can be produced similarly (see Problem 9). $$ \begin{pmatrix} a &b  &c  \\ d &e  &f  \\ g &h  &i \end{pmatrix} $$ is nonsingular iff $$ aei+bfg+cdh-hfa-idb-gec \neq 0 $$ With these cases in mind, we posit a family of formulas, $$a$$, $$ad-bc$$, etc. For each $$n$$ the formula gives rise to a determinant function $$\det\nolimits_{n \! \times \! n}:\mathcal{M}_{n \! \times \! n}\to \mathbb{R}$$ such that an $$n \! \times \! n$$ matrix $$T$$ is nonsingular if and only if $$\det\nolimits_{n \! \times \! n}(T)\neq 0$$. (We usually omit the subscript because if $$ T $$ is $$ n \! \times \! n $$ then "$$ \det(T) $$" could only mean "$$ \det\nolimits_{n \! \times \! n}(T) $$".)


text:
C++ Programming/Code/Standard C Library/Functions/tolower

tolower
The function tolower returns the lowercase version of the character ch.

 * Related topics: isupper - toupper


text:
Linear Algebra/Determinants

In the first chapter of this book we considered linear systems and we picked out the special case of systems with the same number of equations as unknowns, those of the form $$ T\vec{x}=\vec{b} $$ where $$T$$ is a square matrix. We noted a distinction between two classes of $$T$$'s. While such systems may have a unique solution or no solutions or infinitely many solutions, if a particular $$T$$ is associated with a unique solution in any system, such as the homogeneous system $$\vec{b}=\vec{0}$$, then $$T$$ is associated with a unique solution for every $$\vec{b}$$. We call such a matrix of coefficients "nonsingular". The other kind of $$T$$, where every linear system for which it is the matrix of coefficients has either no solution or infinitely many solutions, we call "singular".

Through the second and third chapters the value of this distinction has been a theme. For instance, we now know that nonsingularity of an $$ n \! \times \! n $$ matrix $$ T $$ is equivalent to each of these: So when we look at a particular square matrix, the question of whether it is nonsingular is one of the first things that we ask. This chapter develops a formula to determine this. (Since we will restrict the discussion to square matrices, in this chapter we will usually simply say "matrix" in place of "square matrix".)
 * 1) a system $$ T\vec{x}=\vec{b} $$ has a solution, and that solution is unique;
 * 2) Gauss-Jordan reduction of $$T$$ yields an identity matrix;
 * 3) the rows of $$T$$ form a linearly independent set;
 * 4) the columns of $$ T $$ form a basis for $$ \mathbb{R}^n $$;
 * 5) any map that $$ T $$ represents is an isomorphism;
 * 6) an inverse matrix $$ T^{-1} $$ exists.

More precisely, we will develop infinitely many formulas, one for $$1 \! \times \! 1$$ matrices, one for $$2 \! \times \! 2$$ matrices, etc. Of course, these formulas are related — that is, we will develop a family of formulas, a scheme that describes the formula for each size.

title: Linear Algebra/Determinants


text:
Adventist Youth Honors Answer Book/Insect/Mecoptera

|


text:
C++ Programming/Code/Standard C Library/Functions/isupper

isupper
The isupper function returns non-zero if its argument is an uppercase letter. Otherwise, zero is returned.

 * Related topics: islower - tolower


text:
Linear Algebra/Exploration

''This subsection is optional. It briefly describes how an investigator might come to a good general definition, which is given in the next subsection.''

The three cases above don't show an evident pattern to use for the general $$n \! \times \! n$$ formula. We may spot that the $$1 \! \times \! 1$$ term $$ a $$ has one letter, that the $$2 \! \times \! 2$$ terms $$ad$$ and $$bc$$ have two letters, and that the $$3 \! \times \! 3$$ terms $$aei$$, etc., have three letters. We may also observe that in those terms there is a letter from each row and column of the matrix, e.g., the letters in the $$cdh$$ term

\begin{pmatrix} &   &c \\ d          \\ &h \end{pmatrix} $$

come one from each row and one from each column. But these observations perhaps seem more puzzling than enlightening. For instance, we might wonder why some of the terms are added while others are subtracted.

A good problem solving strategy is to see what properties a solution must have and then search for something with those properties. So we shall start by asking what properties we require of the formulas.

At this point, our primary way to decide whether a matrix is singular is to do Gaussian reduction and then check whether the diagonal of resulting echelon form matrix has any zeroes (that is, to check whether the product down the diagonal is zero). So, we may expect that the proof that a formula determines singularity will involve applying Gauss' method to the matrix, to show that in the end the product down the diagonal is zero if and only if the determinant formula gives zero. This suggests our initial plan: we will look for a family of functions with the property of being unaffected by row operations and with the property that a determinant of an echelon form matrix is the product of its diagonal entries. Under this plan, a proof that the functions determine singularity would go, "Where $$T\rightarrow\cdots\rightarrow\hat{T}$$ is the Gaussian reduction, the determinant of $$T$$ equals the determinant of $$\hat{T}$$ (because the determinant is unchanged by row operations), which is the product down the diagonal, which is zero if and only if the matrix is singular". In the rest of this subsection we will test this plan on the $$2 \! \times \! 2$$ and $$3 \! \times \! 3$$ determinants that we know. We will end up modifying the "unaffected by row operations" part, but not by much.

The first step in checking the plan is to test whether the $$2 \! \times \! 2$$ and $$3 \! \times \! 3$$ formulas are unaffected by the row operation of pivoting: if

T \xrightarrow[]{k\rho_i+\rho_j} \hat{T} $$

then is $$ \det(\hat{T})=\det(T) $$? This check of the $$2 \! \times \! 2$$ determinant after the $$k\rho_1+\rho_2$$ operation

\det( \begin{pmatrix} a    &b       \\ ka+c  &kb+d    \\ \end{pmatrix} ) = a(kb+d)-(ka+c)b = ad-bc $$

shows that it is indeed unchanged, and the other $$2 \! \times \! 2$$ pivot $$k\rho_2+\rho_1$$ gives the same result. The $$3 \! \times \! 3$$ pivot $$k\rho_3+\rho_2$$ leaves the determinant unchanged

 * $$\begin{array}{rl}

\det( \begin{pmatrix} a   &b    &c    \\ kg+d &kh+e &ki+f \\ g    &h    &i \end{pmatrix} ) &=\begin{array}{l} a(kh+e)i+b(ki+f)g+c(kg+d)h \\ \ -h(ki+f)a-i(kg+d)b-g(kh+e)c \end{array}                                \\ &=aei + bfg + cdh - hfa - idb - gec \end{array}$$

as do the other $$3 \! \times \! 3$$ pivot operations.

So there seems to be promise in the plan. Of course, perhaps the $$4 \! \times \! 4$$ determinant formula is affected by pivoting. We are exploring a possibility here and we do not yet have all the facts. Nonetheless, so far, so good.

The next step is to compare $$ \det(\hat{T}) $$ with $$ \det(T) $$ for the operation

T \xrightarrow[]{ {\rho}_i \leftrightarrow {\rho}_j } \hat{T} $$

of swapping two rows. The $$2 \! \times \! 2$$ row swap $$\rho_1\leftrightarrow\rho_2$$

\det( \begin{pmatrix} c &d \\ a  &b \end{pmatrix} ) = cb - ad $$

does not yield $$ ad-bc $$. This $$\rho_1\leftrightarrow\rho_3$$ swap inside of a $$3 \! \times \! 3$$ matrix

\det( \begin{pmatrix} g &h  &i \\ d  &e  &f \\ a  &b  &c \end{pmatrix} ) = gec + hfa + idb - bfg - cdh - aei $$

also does not give the same determinant as before the swap — again there is a sign change. Trying a different $$3 \! \times \! 3$$ swap $$\rho_1\leftrightarrow\rho_2$$

\det( \begin{pmatrix} d &e  &f \\ a  &b  &c \\ g  &h  &i \end{pmatrix} ) = dbi + ecg + fah - hcd - iae - gbf $$

also gives a change of sign.

Thus, row swaps appear to change the sign of a determinant. This modifies our plan, but does not wreck it. We intend to decide nonsingularity by considering only whether the determinant is zero, not by considering its sign. Therefore, instead of expecting determinants to be entirely unaffected by row operations, will look for them to change sign on a swap.

To finish, we compare $$ \det(\hat{T}) $$ to $$ \det(T) $$ for the operation

T \xrightarrow[]{ k{\rho}_i } \hat{T} $$

of multiplying a row by a scalar $$k\neq 0$$. One of the $$2 \! \times \! 2$$ cases is

\det( \begin{pmatrix} a  &b   \\ kc  &kd \end{pmatrix} ) = a(kd) - (kc)b =k\cdot (ad-bc) $$

and the other case has the same result. Here is one $$3 \! \times \! 3$$ case

 * $$\begin{array}{rl}

\det( \begin{pmatrix} a   &b    &c   \\ d    &e    &f   \\ kg   &kh   &ki \end{pmatrix} ) &= \begin{array}{l} ae(ki) + bf(kg) + cd(kh)               \\ \quad -(kh)fa - (ki)db - (kg)ec \end{array}                                     \\ &= k\cdot(aei + bfg + cdh - hfa - idb - gec) \end{array}$$

and the other two are similar. These lead us to suspect that multiplying a row by $$k$$ multiplies the determinant by $$k$$. This fits with our modified plan because we are asking only that the zeroness of the determinant be unchanged and we are not focusing on the determinant's sign or magnitude.

In summary, to develop the scheme for the formulas to compute determinants, we look for determinant functions that remain unchanged under the pivoting operation, that change sign on a row swap, and that rescale on the rescaling of a row. In the next two subsections we will find that for each $$n$$ such a function exists and is unique.

For the next subsection, note that, as above, scalars come out of each row without affecting other rows. For instance, in this equality

\det( \begin{pmatrix} 3 &3  &9  \\ 2  &1  &1  \\ 5  &10 &-5 \end{pmatrix} ) =3 \cdot \det( \begin{pmatrix} 1 &1  &3  \\ 2  &1  &1  \\ 5  &10 &-5 \end{pmatrix} ) $$

the $$3$$ isn't factored out of all three rows, only out of the top row. The determinant acts on each row of independently of the other rows. When we want to use this property of determinants, we shall write the determinant as a function of the rows: "$$ \det (\vec{\rho}_1,\vec{\rho}_2,\dots\vec{\rho}_n) $$", instead of as "$$ \det(T) $$" or "$$ \det(t_{1,1},\dots,t_{n,n}) $$". The definition of the determinant that starts the next subsection is written in this way.

Exercises
/Solutions/

title: Linear Algebra/Exploration


text:
C++ Programming/Code/Standard C Library/Functions/islower

islower
The islower function returns non-zero if its argument is a lowercase letter. Otherwise, zero is returned.

 * Related topics: isupper


text:
Linear Algebra/Properties of Determinants

As described above, we want a formula to determine whether an $$n \! \times \! n$$ matrix is nonsingular. We will not begin by stating such a formula. Instead, we will begin by considering the function that such a formula calculates. We will define the function by its properties, then prove that the function with these properties exists and is unique and also describe formulas that compute this function. (Because we will show that the function exists and is unique, from the start we will say "$$ \det(T) $$" instead of "if there is a determinant function then $$ \det(T) $$" and "the determinant" instead of "any determinant".)

The first result shows that a function satisfying these conditions gives a criteria for nonsingularity. (Its last sentence is that, in the context of the first three conditions, (4) is equivalent to the condition that the determinant of an echelon form matrix is the product down the diagonal.)

That result gives us a way to compute the value of a determinant function on a matrix. Do Gaussian reduction, keeping track of any changes of sign caused by row swaps and any scalars that are factored out, and then finish by multiplying down the diagonal of the echelon form result. This procedure takes the same time as Gauss' method and so is sufficiently fast to be practical on the size matrices that we see in this book.

The prior example illustrates an important point. Although we have not yet found a $$4 \! \times \! 4$$ determinant formula, if one exists then we know what value it gives to the matrix — if there is a function with properties (1)-(4) then on the above matrix the function must return $$5$$.

The "if there is an $$n \! \times \! n$$ determinant function" emphasizes that, although we can use Gauss' method to compute the only value that a determinant function could possibly return, we haven't yet shown that such a determinant function exists for all $$n$$. In the rest of the section we will produce determinant functions.

Exercises
''For these, assume that an $$n \! \times \! n$$ determinant function exists for all $$n$$.''

/Solutions/


text:
Linear Algebra/The Permutation Expansion

The prior subsection defines a function to be a determinant if it satisfies four conditions and shows that there is at most one $$n \! \times \! n$$ determinant function for each $$n$$. What is left is to show that for each $$n$$ such a function exists.

How could such a function not exist? After all, we have done computations that start with a square matrix, follow the conditions, and end with a number.

The difficulty is that, as far as we know, the computation might not give a well-defined result. To illustrate this possibility, suppose that we were to change the second condition in the definition of determinant to be that the value of a determinant does not change on a row swap. By Remark 2.2 we know that this conflicts with the first and third conditions. Here is an instance of the conflict: here are two Gauss' method reductions of the same matrix, the first without any row swap

\begin{pmatrix} 1 &2  \\ 3  &4 \end{pmatrix} \xrightarrow[]{-3\rho_1+\rho_2} \begin{pmatrix} 1 &2  \\ 0  &-2 \end{pmatrix} $$

and the second with a swap.

\begin{pmatrix} 1 &2  \\ 3  &4 \end{pmatrix} \xrightarrow[]{\rho_1\leftrightarrow\rho_2} \begin{pmatrix} 3 &4  \\ 1  &2 \end{pmatrix} \xrightarrow[]{-(1/3)\rho_1+\rho_2} \begin{pmatrix} 3 &4  \\ 0  &2/3 \end{pmatrix} $$

Following Definition 2.1 gives that both calculations yield the determinant $$-2$$ since in the second one we keep track of the fact that the row swap changes the sign of the result of multiplying down the diagonal. But if we follow the supposition and change the second condition then the two calculations yield different values, $$-2$$ and $$2$$. That is, under the supposition the outcome would not be well-defined — no function exists that satisfies the changed second condition along with the other three.

Of course, observing that Definition 2.1 does the right thing in this one instance is not enough; what we will do in the rest of this section is to show that there is never a conflict. The natural way to try this would be to define the determinant function with: "The value of the function is the result of doing Gauss' method, keeping track of row swaps, and finishing by multiplying down the diagonal". (Since Gauss' method allows for some variation, such as a choice of which row to use when swapping, we would have to fix an explicit algorithm.) Then we would be done if we verified that this way of computing the determinant satisfies the four properties. For instance, if $$T$$ and $$\hat{T}$$ are related by a row swap then we would need to show that this algorithm returns determinants that are negatives of each other. However, how to verify this is not evident. So the development below will not proceed in this way. Instead, in this subsection we will define a different way to compute the value of a determinant, a formula, and we will use this way to prove that the conditions are satisfied.

The formula that we shall use is based on an insight gotten from property (3) of the definition of determinants. This property shows that determinants are not linear.

Since scalars come out a row at a time, we might guess that determinants are linear a row at a time.

Multilinearity allows us to expand a determinant into a sum of determinants, each of which involves a simple matrix.

So an $$ n \! \times \! n $$ determinant expands into a sum of $$ n^n $$ determinants where each row of each summands contains a single entry from the starting matrix. However, many of these summand determinants are zero.

That example illustrates the key idea. We've applied multilinearity to a $$3 \! \times \! 3$$ determinant to get $$3^3$$ separate determinants, each with one distinguished entry per row. We can drop most of these new determinants because the matrices are singular, with one row a multiple of another. We are left with the one-entry-per-row determinants also having only one entry per column (one entry from the original determinant, that is). And, since we can factor scalars out, we can further reduce to only considering determinants of one-entry-per-row-and-column matrices where the entries are ones.

These are permutation matrices. Thus, the determinant can be computed in this three-step way (Step 1) for each permutation matrix, multiply together the entries from the original matrix where that permutation matrix has ones, (Step 2) multiply that by the determinant of the permutation matrix and (Step 3) do that for all permutation matrices and sum the results together.

To state this as a formula, we introduce a notation for permutation matrices. Let $$\iota_j$$ be the row vector that is all zeroes except for a one in its $$j$$-th entry, so that the four-wide $$\iota_2$$ is $$\begin{pmatrix} 0 &1 &0 &0 \end{pmatrix}$$. We can construct permutation matrices by permuting — that is, scrambling —  the numbers $$1$$, $$2$$, ..., $$n$$, and using them as indices on the $$\iota$$'s. For instance, to get a $$ 4 \! \times \! 4 $$ permutation matrix matrix, we can scramble the numbers from $$1$$ to $$4$$ into this sequence $$ \langle 3,2,1,4 \rangle $$ and take the corresponding row vector $$\iota$$'s.

\begin{pmatrix} \iota_{3} \\ \iota_{2} \\ \iota_{1} \\ \iota_{4} \end{pmatrix}= \begin{pmatrix} 0 &0  &1  &0  \\ 0  &1  &0  &0  \\ 1  &0  &0  &0  \\ 0  &0  &0  &1 \end{pmatrix} $$

This formula is often written in summation notation

\left|T\right|= \sum_{\text{permutations }\phi}\!\!\!\! t_{1,\phi(1)}t_{2,\phi(2)}\cdots t_{n,\phi(n)} \left|P_{\phi}\right| $$

read aloud as "the sum, over all permutations $$ \phi $$, of terms having the form $$ t_{1,\phi(1)}t_{2,\phi(2)}\cdots t_{n,\phi(n)} \left|P_{\phi}\right| $$". This phrase is just a restating of the three-step process (Step 1) for each permutation matrix, compute $$ t_{1,\phi(1)}t_{2,\phi(2)}\cdots t_{n,\phi(n)} $$ (Step 2) multiply that by $$ \left|P_{\phi}\right| $$ and (Step 3) sum all such terms together.

Computing a determinant by permutation expansion usually takes longer than Gauss' method. However, here we are not trying to do the computation efficiently, we are instead trying to give a determinant formula that we can prove to be well-defined. While the permutation expansion is impractical for computations, it is useful in proofs. In particular, we can use it for the result that we are after.

The proof is deferred to the following subsection. Also there is the proof of the next result (they share some features).

The consequence of this theorem is that, while we have so far stated results in terms of rows (e.g., determinants are multilinear in their rows, row swaps change the signum, etc.), all of the results also hold in terms of columns. The final result gives examples.

We finish with a summary (although the final subsection contains the unfinished business of proving the two theorems). Determinant functions exist, are unique, and we know how to compute them. As for what determinants are about, perhaps these lines help make it memorable.  Determinant none, Solution: lots or none. Determinant some, Solution: just one.

Exercises
These summarize the notation used in this book for the $$2$$- and $$3$$- permutations. $$\begin{array}{c|cc} i         &1      &2    \\ \hline \phi_1(i) &1      &2     \\ \phi_2(i) &2      &1 \end{array} \qquad \begin{array}{c|ccc} i         &1     &2   &3    \\ \hline \phi_1(i) &1     &2   &3    \\ \phi_2(i) &1     &3   &2    \\ \phi_3(i) &2     &1   &3    \\ \phi_4(i) &2     &3   &1    \\ \phi_5(i) &3     &1   &2    \\ \phi_6(i) &3     &2   &1 \end{array} $$

/Solutions/


text:
Linear Algebra/Determinants Exist

''This subsection is optional. It consists of proofs of two results from the prior subsection. These proofs involve the properties of permutations, which will not be used later, except in the optional Jordan Canonical Form subsection.''

The prior subsection attacks the problem of showing that for any size there is a determinant function on the set of square matrices of that size by using multilinearity to develop the permutation expansion.

 * $$\begin{array}{rl}

\begin{vmatrix} t_{1,1} &t_{1,2}  &\ldots  &t_{1,n}  \\ t_{2,1} &t_{2,2}  &\ldots  &t_{2,n}  \\ &\vdots                     \\ t_{n,1} &t_{n,2}  &\ldots  &t_{n,n} \end{vmatrix} &= \begin{array}{l} t_{1,\phi_1(1)}t_{2,\phi_1(2)}\cdots t_{n,\phi_1(n)}\left|P_{\phi_1}\right|      \\ \quad+t_{1,\phi_2(1)}t_{2,\phi_2(2)}\cdots t_{n,\phi_2(n)}\left|P_{\phi_2}\right|      \\ \quad\vdots                             \\ \quad+t_{1,\phi_k(1)}t_{2,\phi_k(2)}\cdots t_{n,\phi_k(n)}\left|P_{\phi_k}\right| \end{array}                                                \\ &=\displaystyle\sum_{\text{permutations }\phi} t_{1,\phi(1)}t_{2,\phi(2)}\cdots t_{n,\phi(n)} \left|P_{\phi}\right| \end{array}$$

This reduces the problem to showing that there is a determinant function on the set of permutation matrices of that size.

Of course, a permutation matrix can be row-swapped to the identity matrix and to calculate its determinant we can keep track of the number of row swaps. However, the problem is still not solved. We still have not shown that the result is well-defined. For instance, the determinant of

P_{\phi}= \begin{pmatrix} 0 &1  &0  &0 \\ 1  &0  &0  &0 \\ 0  &0  &1  &0 \\ 0  &0  &0  &1 \end{pmatrix} $$

could be computed with one swap

P_{\phi} \xrightarrow[]{\rho_1\leftrightarrow\rho_2} \begin{pmatrix} 1 &0  &0  &0 \\ 0  &1  &0  &0 \\ 0  &0  &1  &0 \\ 0  &0  &0  &1 \end{pmatrix} $$

or with three.

P_{\phi} \xrightarrow[]{\rho_3\leftrightarrow\rho_1} \begin{pmatrix} 0 &0  &1  &0 \\ 1  &0  &0  &0 \\ 0  &1  &0  &0 \\ 0  &0  &0  &1 \end{pmatrix} \xrightarrow[]{\rho_2\leftrightarrow\rho_3} \begin{pmatrix} 0 &0  &1  &0 \\ 0  &1  &0  &0 \\ 1  &0  &0  &0 \\ 0  &0  &0  &1 \end{pmatrix} \xrightarrow[]{\rho_1\leftrightarrow\rho_3} \begin{pmatrix} 1 &0  &0  &0 \\ 0  &1  &0  &0 \\ 0  &0  &1  &0 \\ 0  &0  &0  &1 \end{pmatrix} $$

Both reductions have an odd number of swaps so we figure that $$ \left|P_{\phi}\right|=-1 $$ but how do we know that there isn't some way to do it with an even number of swaps? Corollary 4.6 below proves that there is no permutation matrix that can be row-swapped to an identity matrix in two ways, one with an even number of swaps and the other with an odd number of swaps.

We still have not shown that the permutation expansion is well-defined because we have not considered row operations on permutation matrices other than row swaps. We will finesse this problem: we will define a function $$ d:\mathcal{M}_{n \! \times \! n}\to \mathbb{R} $$ by altering the permutation expansion formula, replacing $$\left|P_\phi\right|$$ with $$\sgn(\phi)$$

d(T)= \sum_{\text{permutations }\phi}t_{1,\phi(1)}t_{2,\phi(2)}\dots t_{n,\phi(n)} \sgn(\phi) $$

(this gives the same value as the permutation expansion because the prior result shows that $$\det(P_\phi)=\sgn(\phi)$$). This formula's advantage is that the number of inversions is clearly well-defined — just count them. Therefore, we will show that a determinant function exists for all sizes by showing that $$ d $$ is it, that is, that $$d$$ satisfies the four conditions.

We have now shown that determinant functions exist for each size. We already know that for each size there is at most one determinant. Therefore, the permutation expansion computes the one and only determinant value of a square matrix.

We end this subsection by proving the other result remaining from the prior subsection, that the determinant of a matrix equals the determinant of its transpose.

Exercises
These summarize the notation used in this book for the $$2$$- and $$3$$- permutations. $$ \begin{array}{c|cc} i         &1      &2    \\ \hline \phi_1(i) &1      &2     \\ \phi_2(i) &2      &1 \end{array} \qquad \begin{array}{c|ccc} i         &1     &2   &3    \\ \hline \phi_1(i) &1     &2   &3    \\ \phi_2(i) &1     &3   &2    \\ \phi_3(i) &2     &1   &3    \\ \phi_4(i) &2     &3   &1    \\ \phi_5(i) &3     &1   &2    \\ \phi_6(i) &3     &2   &1 \end{array} $$

/Solutions/

title: Linear Algebra/Determinants Exist


text:
C++ Programming/Code/Standard C Library/Functions/toupper

toupper
The toupper function returns the uppercase version of the character ch.

 * Related topics: tolower


text:
Linear Algebra/Geometry of Determinants

The prior section develops the determinant algebraically, by considering what formulas satisfy certain properties. This section complements that with a geometric approach. One advantage of this approach is that, while we have so far only considered whether or not a determinant is zero, here we shall give a meaning to the value of that determinant. (The prior section handles determinants as functions of the rows, but in this section columns are more convenient. The final result of the prior section says that we can make the switch.)

title: Linear Algebra/Geometry of Determinants


text:
Linear Algebra/Determinants as Size Functions

This parallelogram picture is familiar from the construction of the sum of the two vectors. One way to compute the area that it encloses is to draw this rectangle and subtract the area of each subregion. $$\begin{array}{l} \text{area of parallelogram}                   \\ \quad =\text{area of rectangle} -\text{area of }A-\text{area of }B \\ \qquad -\cdots-\text{area of }F                  \\ \quad =(x_1+x_2)(y_1+y_2)-x_2y_1-x_1y_1/2       \\ \qquad -x_2y_2/2-x_2y_2/2-x_1y_1/2-x_2y_1        \\ \quad =x_1y_2-x_2y_1 \end{array}$$ The fact that the area equals the value of the determinant

\begin{vmatrix} x_1 &x_2  \\ y_1 &y_2 \end{vmatrix} =x_1y_2-x_2y_1 $$

is no coincidence. The properties in the definition of determinants make reasonable postulates for a function that measures the size of the region enclosed by the vectors in the matrix.

For instance, this shows the effect of multiplying one of the box-defining vectors by a scalar (the scalar used is $$k=1.4$$). The region formed by $$k\vec{v}$$ and $$\vec{w}$$ is bigger, by a factor of $$ k $$, than the shaded region enclosed by $$\vec{v}$$ and $$\vec{w}$$. That is, $$ \text{size}\, (k\vec{v},\vec{w})=k\cdot\text{size}\, (\vec{v},\vec{w}) $$ and in general we expect of the size measure that $$\text{size}\, (\dots,k\vec{v},\dots)=k\cdot\text{size}\, (\dots,\vec{v},\dots)$$. Of course, this postulate is already familiar as one of the properties in the defintion of determinants.

Another property of determinants is that they are unaffected by pivoting. Here are before-pivoting and after-pivoting boxes (the scalar used is $$k=0.35$$). Although the region on the right, the box formed by $$v$$ and $$k\vec{v}+\vec{w}$$, is more slanted than the shaded region, the two have the same base and the same height and hence the same area. This illustrates that $$ \text{size}\, (\vec{v},k\vec{v}+\vec{w})=\text{size}\, (\vec{v},\vec{w}) $$. Generalized, $$\text{size}\, (\dots,\vec{v},\dots,\vec{w},\dots) =\text{size}\, (\dots,\vec{v},\dots,k\vec{v}+\vec{w},\dots)$$, which is a restatement of the determinant postulate.

Of course, this picture shows that $$ \text{size}\, (\vec{e}_1,\vec{e}_2)=1 $$, and we naturally extend that to any number of dimensions $$\text{size}\,(\vec{e}_1,\dots,\vec{e}_n)=1$$, which is a restatement of the property that the determinant of the identity matrix is one.

With that, because property (2) of determinants is redundant (as remarked right after the definition), we have that all of the properties of determinants are reasonable to expect of a function that gives the size of boxes. We can now cite the work done in the prior section to show that the determinant exists and is unique to be assured that these postulates are consistent and sufficient (we do not need any more postulates). That is, we've got an intuitive justification to interpret $$ \det(\vec{v}_1,\dots,\vec{v}_n) $$ as the size of the box formed by the vectors. (Comment. An even more basic approach, which also leads to the definition below, is in.

The definition of volume gives a geometric interpretation to something in the space, boxes made from vectors. The next result relates the geometry to the functions that operate on spaces.

The two sentences state the same idea, first in map terms and then in matrix terms. Although we tend to prefer a map point of view, the second sentence, the matrix version, is more convienent for the proof and is also the way that we shall use this result later. (Alternate proofs are given as Problem 16 and Problem 21].)

Recall that determinants are not additive homomorphisms, $$\det(A+B)$$ need not equal $$\det(A)+\det(B)$$. The above theorem says, in contrast, that determinants are multiplicative homomorphisms: $$\det(AB)$$ does equal $$\det(A)\cdot \det(B)$$.

Exercises
/Solutions/


text:
Linear Algebra/Other Formulas for Determinants

(This section is optional. Later sections do not depend on this material.)

Determinants are a fount of interesting and amusing formulas. Here is one that is often seen in calculus classes and used to compute determinants by hand.


text:
Linear Algebra/Laplace's Expansion

We finish by applying this result to derive a new formula for the inverse of a matrix. With Theorem 1.5, the determinant of an $$ n \! \times \! n $$ matrix $$ T $$ can be calculated by taking linear combinations of entries from a row and their associated cofactors.

t_{i,1}\cdot T_{i,1}+t_{i,2}\cdot T_{i,2}+\dots+t_{i,n}\cdot T_{i,n} =\left|T\right| \qquad (*) $$

Recall that a matrix with two identical rows has a zero determinant. Thus, for any matrix $$ T $$, weighing the cofactors by entries from the "wrong" row — row $$k$$ with $$k\neq i$$ —  gives zero

t_{i,1}\cdot T_{k,1}+t_{i,2}\cdot T_{k,2}+\dots+t_{i,n}\cdot T_{k,n}=0 \qquad (**)$$

because it represents the expansion along the row $$k$$ of a matrix with row $$ i $$ equal to row $$ k $$. This equation summarizes ($$*$$) and ($$**$$).

\left( \begin{array}{cccc} t_{1,1} &t_{1,2}  &\ldots  &t_{1,n}\\ t_{2,1}  &t_{2,2}  &\ldots  &t_{2,n}  \\ &\vdots\\ t_{n,1} &t_{n,2} &\ldots  &t_{n,n} \end{array} \right) \begin{pmatrix} T_{1,1} &T_{2,1}  &\ldots  &T_{n,1}  \\ T_{1,2} &T_{2,2}  &\ldots  &T_{n,2}  \\ &\vdots  &        &         \\ T_{1,n} &T_{2,n}  &\ldots  &T_{n,n} \end{pmatrix} =\begin{pmatrix} 0       &|T|      &\ldots  &0        \\ &\vdots  &        &         \\ 0       &0        &\ldots  &|T| \end{pmatrix} $$
 * T|     &0        &\ldots  &0        \\

Note that the order of the subscripts in the matrix of cofactors is opposite to the order of subscripts in the other matrix; e.g., along the first row of the matrix of cofactors the subscripts are $$1,1$$ then $$2,1$$, etc.

The formulas from this section are often used for by-hand calculation and are sometimes useful with special types of matrices. However, they are not the best choice for computation with arbitrary matrices because they require more arithmetic than, for instance, the Gauss-Jordan method.

Exercises
/Solutions/

title: Linear Algebra/Laplace's Expansion


text:
Adventist Youth Honors Answer Book/Insect/Siphonaptera

/Transcluded Modules


text:
Linear Algebra/Topic: Cramer's Rule

We have introduced determinant functions algebraically by looking for a formula to decide whether a matrix is nonsingular. After that introduction we saw a geometric interpretation, that the determinant function gives the size of the box with sides formed by the columns of the matrix. This Topic makes a connection between the two views.

First, a linear system

\begin{array}{*{2}{rc}r} x_1 &+  &2x_2  &=  &6  \\ 3x_1 &+  &x_2   &=  &8 \end{array} $$

is equivalent to a linear relationship among vectors.

x_1\cdot\begin{pmatrix} 1 \\ 3 \end{pmatrix}+x_2\cdot\begin{pmatrix} 2 \\ 1 \end{pmatrix}=\begin{pmatrix} 6 \\ 8 \end{pmatrix} $$

The picture below shows a parallelogram with sides formed from $$\binom{1}{3}$$ and $$\binom{2}{1}$$ nested inside a parallelogram with sides formed from $$x_1\binom{1}{3}$$ and $$x_2\binom{2}{1}$$. So even without determinants we can state the algebraic issue that opened this book, finding the solution of a linear system, in geometric terms: by what factors $$x_1$$ and $$x_2$$ must we dilate the vectors to expand the small parallegram to fill the larger one?

However, by employing the geometric significance of determinants we can get something that is not just a restatement, but also gives us a new insight and sometimes allows us to compute answers quickly. Compare the sizes of these shaded boxes. The second is formed from $$x_1\binom{1}{3}$$ and $$\binom{2}{1}$$, and one of the properties of the size function— the determinant— is that its size is therefore $$ x_1 $$ times the size of the first box. Since the third box is formed from $$x_1\binom{1}{3}+x_2\binom{2}{1}=\binom{6}{8}$$ and $$\binom{2}{1}$$, and the determinant is unchanged by adding $$x_2$$ times the second column to the first column, the size of the third box equals that of the second. We have this.

\begin{vmatrix} 6 &2  \\ 8  &1 \end{vmatrix} = \begin{vmatrix} x_1\cdot 1 &2  \\ x_1\cdot 3 &1 \end{vmatrix} = x_1\cdot \begin{vmatrix} 1 &2  \\ 3  &1 \end{vmatrix} $$

Solving gives the value of one of the variables.

x_1= \frac{\begin{vmatrix} 6 &2  \\ 8  &1 \end{vmatrix} }{ \begin{vmatrix} 1 &2  \\ 3  &1 \end{vmatrix}  } =\frac{-10}{-5}=2 $$

The theorem that generalizes this example, Cramer's Rule, is: if $$ \left|A\right|\neq 0 $$ then the system $$ A\vec{x}=\vec{b} $$ has the unique solution $$ x_i=\left|B_i\right|/\left|A\right| $$ where the matrix $$B_i$$ is formed from $$A$$ by replacing column $$i$$ with the vector $$ \vec{b} $$. Problem 3 asks for a proof.

For instance, to solve this system for $$ x_2 $$

\begin{pmatrix} 1 &0  &4  \\ 2  &1  &-1 \\ 1  &0  &1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} =\begin{pmatrix} 2 \\ 1 \\ -1 \end{pmatrix} $$

we do this computation.

x_2= \frac{ \begin{vmatrix} 1 &2  &4  \\ 2  &1  &-1 \\ 1  &-1 &1 \end{vmatrix}  }{ \begin{vmatrix} 1 &0  &4  \\ 2  &1  &-1 \\ 1  &0  &1 \end{vmatrix}  } =\frac{-18}{-3} $$

Cramer's Rule allows us to solve many two equations/two unknowns systems by eye. It is also sometimes used for three equations/three unknowns systems. But computing large determinants takes a long time, so solving large systems by Cramer's Rule is not practical.

Exercises
/Solutions/

title: Linear Algebra/Topic: Cramer's Rule