text:
User:Rwhelan3

Charter and Magnet Schools as a part of Educational Reform

Introduction

Education is defined as a process by which people develop their minds, their character and their skills. This life long process is marked by a person’s constant change and development. The instruction in a school that is controlled by the government is what we define as schooling. These definitions overlap each other in that education is continual and schooling is one part of a person’s education. Educational reform has been part of the education system for the past one hundred years (Ryan & M.Cooper, 2000). As the progression of educational reform proceeded to take large strides throughout the years the development of charter and magnet schools have clearly proven to be a valuable part of its progression, and while different, they seem to have the same goals in offering an alternative to the public education system without having to pay private school tuitions.

Magnet Schools

Magnet schools are part of the public school system that typically exist outside of zoned areas. These schools usually have something special to offer over standard public schools. The schools were first brought about to help increase the diversity in schools while making it an attractive choice to students and parents. Magnet schools have a tendency to attract students outside of their assigned neighborhood while offering an alternative curriculum and instructional approach. Although the main purpose of magnet schools was to reduce racial segregation voluntarily it has now moved to increasing academic achievement. In order to do this, magnet schools have adopted cooperative learning techniques, extracurricular activities, and special projects that allow students to share their diverse skills. Student s evaluations are based on progress and effort as well as achievement. Their grades may be written as comments rather than grades, which in turn will lessen the tendency to stereotype or create hierarchy among students. Therefore magnet schools have shifted from desegregating to creating schools with high interest, motivation, and learning for students with the support and satisfaction of parents. (Hadderman, 2002) These schools serve as pilots for effective educational change. (Klauke, 1988)

Magnet School Statistics

During 1991-92, districts across the country operated 2,400 magnet schools and 3,200 individual magnet programs making it the most prevalent choice. Student surveys show that graduates of magnet programs compared with graduates of comprehensive urban high schools suggest that magnets can positively influence high school graduates’ social development and educational/occupational aspirations. Two long-term studies also confirm the academics suitability for high risk and other youth (Hadderman, 2002). Although these studies show favorable findings there are some that show negative or mixed results for magnet schools. For example, Steel and Eaton’s 1996 evaluation of the Magnet Schools assistance program between 1989-1991discovered that only half the schools met their desegregation objectives during the grant period. (Hadderman, 2002) This supports the theory that magnets selection processes which vary among districts, draw only the best students and teachers. Therefore to establish and maintain magnet objectives, principals often need to play a stronger than usual role in shaping policy (Klauke, 1988).

Charter Schools

Charter schools are nonsectarian public schools that operate with freedom from the regulations that apply to public schools. The “charter” establishing each school is a performance contract detailing the schools mission, goals, program, methods of assessment, students served, and ways to measure success. They are held accountable by their sponsor, which is usually a state or local board. The basic concept of the charter school is that they exercise increased autonomy in return for this accountability. They are accountable for both academic and fiscal practices to several groups, the sponsor that grants them, the parents who choose them, and the public that funds them. In order to start a charter school the state must first set in effect a charter law. Then the founders of the school apply to the state to start the school and receive funding. Charter schools are public schools they are funded by enrollment so they receive funding from the district and the state according to the number of students. The intention of the charter school is to increase the opportunity for quality education, create a choice for parents in the public school system, encourage innovative teaching, create new professional opportunism for teachers, and encourage community and parent involvement in the students’ education. Charter schools give families the chance to pick schools that best fit their child’s educational well-being. Some charter school programs focus on reading and writing and additional subjects students struggle on, while other schools offer special arts and music programs. They also offer dropout prevention programs, adult education programs, preschool programs(Head Start), day care needs, and programs that work with children who want to go to college (just the FAQs- Charter schools, 2008). Charter schools focus on the needs of students not adults. Their goal being to help children succeed no matter what. They often engage local businesses to provide resources and services to the local school and families. Teachers often choose charter schools because they help them avoid the frustration of bureaucracy. In addition to hiring certified teachers charter schools can hire qualified individuals with professional experience in their subject area this allows education with a real-life experience. As stated in the No Child Left Behind Policy school choice programs aim to increase education options for students and their families and reconfigure the landscape of education in America (Krueger & Ziebarth, 2001). Charter schools are considered part of the school choice program.

Charter School Statistics

Charter schools have become a very popular choice in the public school system. The Center for Education Reform’s 2001-02 National Charter School Directory profiles 2’431 schools in 34 states and Washington D.C. these schools serve nearly 580,000 children and involve more than 1.6 million people, including students, parents, teachers, administrators, and charter school board members (Hadderman, 2002). As a whole charter schools have been successful by providing an exciting new education in an inclusive, individual matter. Harvard University Professor and Economist Caroline Hoxby recently released a study called “A Straightforward Comparison of Charter Schools and Regular Public Schools in the United States.” The study compared 4th graders in charter schools to 4th graders in public schools that the charter students would go to absent the charter option and made several conclusions. Compared to the students in the nearest public school, charter school students are 4% more likely to be proficient in reading and 2% are more likely to be proficient in math on the states exams. Students compared with the nearest regular public school with similar racial composition, the charter school students were 5% more likely to be proficient in reading and 3% more likely to be proficient in math. In states where charters are well established, such as Arizona and California the advantage tends to be greater (just the FAQs- Charter schools, 2008).

Conclusion

In conclusion, charter and magnet schools give an alternative to public schools for students and parents. They are both still held accountable for test scores and enrollment. Magnet schools were developed to desegregate public schools voluntarily while charter schools were developed to offer a better quality education through the public school system. Magnet schools have moved towards providing better education now rather than focusing on desegregation. Both schools offer quality education without having to pay tuition to a private school. They also have the freedom to incorporate special programs as a part of their educational system. As stated in the No Child Left Behind Policy school choice programs aim to increase education options for students and their families and reconfigure the landscape of education in America (Krueger & Ziebarth, 2001). The differences between charter and magnet schools are minimal. Students are admitted in different ways depending on the individual institution. Teachers in magnet schools must be certified whereas in charter schools they can hire qualified individuals with real-life experience in their subject area. While magnet schools are 100% state funded, charter schools require some help from outside sources Charter and magnet schools seem to have the same goals at hand, and that is provide a quality alternative to public education.

Bibliography

Hadderman, M. (2002). School Choice. Trends and Issues. ERIC Clearinghouse on Educational Management. Just The FAQs- Charter schools. (2008, February 14). Retrieved from www.edreform.com. Klauke, A. (1988). Magnet Schools. Eric Clearinghouse on Educational management. Krueger, C., & Ziebarth, T. (2001). School Choice. No Child Left Behind Policy Brief. Education Commision of the States. Ryan, K., & M.Cooper, J. (2000). Those Who Can, Teach. Boston, New York: Houghton Mifflin Company.

title: User:Rwhelan3


text:
Linear Algebra/Gauss' Method

Finding the set of all solutions is solving the system. No guesswork or good fortune is needed to solve a linear system. There is an algorithm that always works. The next example introduces that algorithm, called Gauss' method. It transforms the system, step by step, into one with a form that is easily solved.

Most of this subsection and the next one consists of examples of solving linear systems by Gauss' method. We will use it throughout this book. It is fast and easy. But, before we get to those examples, we will first show that this method is also safe in that it never loses solutions or picks up extraneous solutions.

Each of those three operations has a restriction. Multiplying a row by $$0$$ is not allowed because obviously that can change the solution set of the system. Similarly, adding a multiple of a row to itself is not allowed because adding $$-1$$ times the row to itself has the effect of multiplying the row by $$0$$. Finally, swapping a row with itself is disallowed to make some results in the fourth chapter easier to state and remember (and besides, self-swapping doesn't accomplish anything).

When writing out the calculations, we will abbreviate "row $$i$$" by "$$\rho_i$$". For instance, we will denote a pivot operation by $$k\rho_i+\rho_j$$, with the row that is changed written second. We will also, to save writing, often list pivot steps together when they use the same $$\rho_i$$.

As these examples illustrate, Gauss' method uses the elementary reduction operations to set up back-substitution.

Strictly speaking, the operation of rescaling rows is not needed to solve linear systems. We have included it because we will use it later in this chapter as part of a variation on Gauss' method, the Gauss-Jordan method.

All of the systems seen so far have the same number of equations as unknowns. All of them have a solution, and for all of them there is only one solution. We finish this subsection by seeing for contrast some other things that can happen.

That example's system has more equations than variables. Gauss' method is also useful on systems with more variables than equations. Many examples are in the next subsection.

Another way that linear systems can differ from the examples shown earlier is that some linear systems do not have a unique solution. This can happen in two ways.

The first is that it can fail to have any solution at all.

The other way that a linear system can fail to have a unique solution is to have many solutions.

Don't be fooled by the "$$ 0=0 $$" equation in that example. It is not the signal that a system has many solutions.

We will finish this subsection with a summary of what we've seen so far about Gauss' method.

Gauss' method uses the three row operations to set a system up for back substitution. If any step shows a contradictory equation then we can stop with the conclusion that the system has no solutions. If we reach echelon form without a contradictory equation, and each variable is a leading variable in its row, then the system has a unique solution and we find it by back substitution. Finally, if we reach echelon form without a contradictory equation, and there is not a unique solution (at least one variable is not a leading variable) then the system has many solutions.

The next subsection deals with the third case— we will see how to describe the solution set of a system with many solutions.

Exercises
/Solutions/

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

title: Linear Algebra/Gauss' Method


text:
Linear Algebra/Describing the Solution Set

A linear system with a unique solution has a solution set with one element. A linear system with no solution has a solution set that is empty. In these cases the solution set is easy to describe. Solution sets are a challenge to describe only when they contain many elements.

In the echelon form system derived in the above example, $$x$$ and $$y$$ are leading variables and $$z$$ is free.

We refer to a variable used to describe a family of solutions as a parameter and we say that the set above is parametrized with $$y$$ and $$w$$. (The terms "parameter" and "free variable" do not mean the same thing. Above, $$y$$ and $$w$$ are free because in the echelon form system they do not lead any row. They are parameters because they are used in the solution set description. We could have instead parametrized with $$y$$ and $$z$$ by rewriting the second equation as $$w=\frac23-\frac13z$$ . In that case, the free variables are still $$y$$ and $$w$$, but the parameters are $$y$$ and $$z$$ . Notice that we could not have parametrized with $$x$$ and $$y$$ , so there is sometimes a restriction on the choice of parameters. The terms "parameter" and "free" are related because, as we shall show later in this chapter, the solution set of a system can always be parametrized with the free variables. Consequently, we shall parametrize all of our descriptions in this way.)

We finish this subsection by developing the notation for linear systems and their solution sets that we shall use in the rest of this book.

Matrices are usually named by upper case roman letters, e.g. $$A$$. Each entry is denoted by the corresponding lower-case letter, e.g. $$a_{i,j}$$ is the number in row $$i$$ and column $$j$$ of the array. For instance,
 * $$A=\begin{pmatrix}1&2.2&5\\3&4&-7\end{pmatrix}$$

has two rows and three columns, and so is a $$2\times3$$ matrix. (Read that "two-by-three"; the number of rows is always stated first.) The entry in the second row and first column is $$a_{2,1}=3$$. Note that the order of the subscripts matters: $$a_{1,2}\ne a_{2,1}$$ since $$a_{1,2}=2.2$$. (The parentheses around the array are a typographic device so that when two matrices are side by side we can tell where one ends and the other starts.)

Matrices occur throughout this book. We shall use $$\mathcal{M}_{n\times m}$$ to denote the collection of $$n\times m$$ matrices.

We will also use the array notation to clarify the descriptions of solution sets. A description like $$\{(2-2z+2w,-1+z-w,z,w)\big|z,w\in\R\}$$ from Example 2.3 is hard to read. We will rewrite it to group all the constants together, all the coefficients of $$z$$ together, and all the coefficients of $$w$$ together. We will write them vertically, in one-column wide matrices.

\left\{\begin{pmatrix}2\\-1\\0\\0\end{pmatrix}+\begin{pmatrix}-2\\1\\1\\0\end{pmatrix}z+\begin{pmatrix}2\\-1\\0\\1\end{pmatrix}w\Bigg|z,w\in\R\right\} $$

For instance, the top line says that $$x=2-2z+2w$$. The next section gives a geometric interpretation that will help us picture the solution sets when they are written in this way.

Vectors are an exception to the convention of representing matrices with capital roman letters. We use lower-case roman or greek letters overlined with an arrow: $$\vec a,\vec b$$ ... or $$\vec{\alpha},\vec{\beta}$$ ... (boldface is also common: $$\mathbf{a}$$ or $$ \boldsymbol{\alpha}$$). For instance, this is a column vector with a third component of $$7$$.

 * $$\vec v=\begin{pmatrix}1\\3\\7\end{pmatrix}$$

The style of description of solution sets that we use involves adding the vectors, and also multiplying them by real numbers, such as the $$z$$ and $$w$$. We need to define these operations.

Scalar multiplication can be written in either order: $$r\cdot\vec v$$ or $$\vec v\cdot r$$, or without the "$$\cdot$$" symbol: $$r\vec v$$. (Do not refer to scalar multiplication as "scalar product" because that name is used for a different operation.)

Notice that the definitions of vector addition and scalar multiplication agree where they overlap, for instance, $$\vec v+\vec v=2\vec v$$.

With the notation defined, we can now solve systems in the way that we will use throughout this book.

Before the exercises, we pause to point out some things that we have yet to do.

The first two subsections have been on the mechanics of Gauss' method. Except for one result, Theorem 1.4— without which developing the method doesn't make sense since it says that the method gives the right answers— we have not stopped to consider any of the interesting questions that arise.

For example, can we always describe solution sets as above, with a particular solution vector added to an unrestricted linear combination of some other vectors? The solution sets we described with unrestricted parameters were easily seen to have infinitely many solutions so an answer to this question could tell us something about the size of solution sets. An answer to that question could also help us picture the solution sets, in $$\mathbb{R}^2$$, or in $$\mathbb{R}^3$$, etc.

Many questions arise from the observation that Gauss' method can be done in more than one way (for instance, when swapping rows, we may have a choice of which row to swap with). Theorem 1.4 says that we must get the same solution set no matter how we proceed, but if we do Gauss' method in two different ways must we get the same number of free variables both times, so that any two solution set descriptions have the same number of parameters? Must those be the same variables (e.g., is it impossible to solve a problem one way and get $$y$$ and $$w$$ free or solve it another way and get $$y$$ and $$z$$ free)?

In the rest of this chapter we answer these questions. The answer to each is "yes". The first question is answered in the last subsection of this section. In the second section we give a geometric description of solution sets. In the final section of this chapter we tackle the last set of questions. Consequently, by the end of the first chapter we will not only have a solid grounding in the practice of Gauss' method, we will also have a solid grounding in the theory. We will be sure of what can and cannot happen in a reduction.

Exercises
/Solutions/


text:
Linear Algebra/General = Particular + Homogeneous

Description of Solution Sets
The prior subsection has many descriptions of solution sets. They all fit a pattern. They have a vector that is a particular solution of the system added to an unrestricted combination of some other vectors. The solution set from Example 2.13 illustrates.

\left\{ \underbrace{ \begin{pmatrix} 0 \\ 4 \\ 0 \\ 0 \\ 0 \end{pmatrix}}_{\begin{array}{c}\\[-19pt]\scriptstyle\text{particular} \\[-5pt]\scriptstyle\text{solution}\end{array}}+ \underbrace{w\begin{pmatrix} 1 \\ -1 \\ 3 \\ 1 \\ 0 \end{pmatrix}+ u\begin{pmatrix} 1/2 \\ -1 \\ 1/2 \\ 0 \\ 1 \end{pmatrix}}_{\begin{array}{c}\\[-19pt]\scriptstyle\text{unrestricted}\\[-5pt]\scriptstyle\text{combination}\end{array}} \,\big|\, w,u\in\mathbb{R}\right\} $$

The combination is unrestricted in that $$w$$ and $$u$$ can be any real numbers— there is no condition like "such that $$2w-u=0$$" that would restrict which pairs $$w,u$$ can be used to form combinations.

That example shows an infinite solution set conforming to the pattern. We can think of the other two kinds of solution sets as also fitting the same pattern. A one-element solution set fits in that it has a particular solution, and the unrestricted combination part is a trivial sum (that is, instead of being a combination of two vectors, as above, or a combination of one vector, it is a combination of no vectors). A zero-element solution set fits the pattern since there is no particular solution, and so the set of sums of that form is empty.

We will show that the examples from the prior subsection are representative, in that the description pattern discussed above holds for every solution set.

This description has two parts, the particular solution $$\vec{p}$$ and also the unrestricted linear combination of the $$\vec{\beta}$$'s. We shall prove the theorem in two corresponding parts, with two lemmas.

Homogeneous Systems
We will focus first on the unrestricted combination part. To do that, we consider systems that have the vector of zeroes as one of the particular solutions, so that $$\vec{p}+c_1\vec{\beta}_1+\dots+c_k\vec{\beta}_k$$ can be shortened to $$c_1\vec{\beta}_1+\dots+c_k\vec{\beta}_k$$.

(These are "homogeneous" because all of the terms involve the same power of their variable— the first power— including a "$$ 0x_{0} $$" that we can imagine is on the right side.)

Studying the associated homogeneous system has a great advantage over studying the original system. Nonhomogeneous systems can be inconsistent. But a homogeneous system must be consistent since there is always at least one solution, the vector of zeros.

There are many different zero vectors, e.g., the one-tall zero vector, the two-tall zero vector, etc. Nonetheless, people often refer to "the" zero vector, expecting that the size of the one being discussed will be clear from the context.

We now have the terminology to prove the two parts of Theorem 3.1. The first lemma deals with unrestricted combinations.

Before the proof, we will recall the back substitution calculations that were done in the prior subsection.

Imagine that we have brought a system to this echelon form.

\begin{array}{*{4}{rc}r} x &+  &2y  &-  &z  &+  &2w &=  &0  \\ &  &-3y &+  &z  &   &   &=  &0  \\ &  &    &   &   &   &-w &=  &0 \end{array} $$

We next perform back-substitution to express each variable in terms of the free variable $$z$$. Working from the bottom up, we get first that $$ w $$ is $$ 0\cdot z $$, next that $$ y $$ is $$ (1/3)\cdot z $$, and then substituting those two into the top equation $$ x+2((1/3)z)-z+2(0)=0 $$ gives $$ x=(1/3)\cdot z $$. So, back substitution gives a parametrization of the solution set by starting at the bottom equation and using the free variables as the parameters to work row-by-row to the top. The proof below follows this pattern.

Comment: That is, this proof just does a verification of the bookkeeping in back substitution to show that we haven't overlooked any obscure cases where this procedure fails, say, by leading to a division by zero. So this argument, while quite detailed, doesn't give us any new insights. Nevertheless, we have written it out for two reasons. The first reason is that we need the result— the computational procedure that we employ must be verified to work as promised. The second reason is that the row-by-row nature of back substitution leads to a proof that uses the technique of mathematical induction. This is an important, and non-obvious, proof technique that we shall use a number of times in this book. Doing an induction argument here gives us a chance to see one in a setting where the proof material is easy to follow, and so the technique can be studied. Readers who are unfamiliar with induction arguments should be sure to master this one and the ones later in this chapter before going on to the second chapter.

We say that the set $$\{c_1\vec{\beta}_1+\cdots+c_k\vec{\beta}_k \,\big|\, c_1,\ldots,c_k\in\mathbb{R}\}$$ is generated by or spanned by the set of vectors $$ \{{\vec{\beta}_1},\ldots,{\vec{\beta}_k}\} $$. There is a tricky point to this definition. If a homogeneous system has a unique solution, the zero vector, then we say the solution set is generated by the empty set of vectors. This fits with the pattern of the other solution sets: in the proof above the solution set is derived by taking the $$ c $$'s to be the free variables and if there is a unique solution then there are no free variables.

This proof incidentally shows, as discussed after Example 2.4, that solution sets can always be parametrized using the free variables.

Nonhomogeneous Systems
The next lemma finishes the proof of Theorem 3.1 by considering the particular solution part of the solution set's description.

The two lemmas above together establish Theorem 3.1. We remember that theorem with the slogan "$$ \text{General} = \text{Particular} + \text{Homogeneous} $$".

This table summarizes the factors affecting the size of a general solution.

The factor on the top of the table is the simpler one. When we perform Gauss' method on a linear system, ignoring the constants on the right side and so paying attention only to the coefficients on the left-hand side, we either end with every variable leading some row or else we find that some variable does not lead a row, that is, that some variable is free. (Of course, "ignoring the constants on the right" is formalized by considering the associated homogeneous system. We are simply putting aside for the moment the possibility of a contradictory equation.)

A nice insight into the factor on the top of this table at work comes from considering the case of a system having the same number of equations as variables. This system will have a solution, and the solution will be unique, if and only if it reduces to an echelon form system where every variable leads its row, which will happen if and only if the associated homogeneous system has a unique solution. Thus, the question of uniqueness of solution is especially interesting when the system has the same number of equations as variables.

The above table has two factors. We have already considered the factor along the top: we can tell which column a given linear system goes in solely by considering the system's left-hand side— the constants on the right-hand side play no role in this factor. The table's other factor, determining whether a particular solution exists, is tougher. Consider these two

\begin{array}{*{2}{rc}r} 3x &+ &2y &= &5 \\ 3x &+ &2y &= &5 \end{array} \qquad \begin{array}{*{2}{rc}r} 3x &+ &2y &= &5 \\ 3x &+ &2y &= &4 \end{array} $$

with the same left sides but different right sides. Obviously, the first has a solution while the second does not, so here the constants on the right side decide if the system has a solution. We could conjecture that the left side of a linear system determines the number of solutions while the right side determines if solutions exist, but that guess is not correct. Compare these two systems

\begin{array}{*{2}{rc}r} 3x &+ &2y &= &5 \\ 4x &+ &2y &= &4 \end{array} \qquad \begin{array}{*{2}{rc}r} 3x &+ &2y &= &5 \\ 3x &+ &2y &= &4 \end{array} $$

with the same right sides but different left sides. The first has a solution but the second does not. Thus the constants on the right side of a system don't decide alone whether a solution exists; rather, it depends on some interaction between the left and right sides.

For some intuition about that interaction, consider this system with one of the coefficients left as the parameter $$c$$.

\begin{array}{*{3}{rc}r} x &+  &2y  &+  &3z  &=  &1  \\ x &+  &y   &+  &z   &=  &1  \\ cx &+  &3y  &+  &4z  &=  &0 \end{array} $$

If $$ c=2 $$ this system has no solution because the left-hand side has the third row as a sum of the first two, while the right-hand does not. If $$ c\neq 2 $$ this system has a unique solution (try it with $$ c=1 $$). For a system to have a solution, if one row of the matrix of coefficients on the left is a linear combination of other rows, then on the right the constant from that row must be the same combination of constants from the same rows.

More intuition about the interaction comes from studying linear combinations. That will be our focus in the second chapter, after we finish the study of Gauss' method itself in the rest of this chapter.

Exercises
/Solutions/


text:
Linear Algebra/Comparing Set Descriptions

''This subsection is optional. Later material will not require the work here.''

Comparing Set Descriptions
A set can be described in many different ways. Here are two different descriptions of a single set:

\{\begin{pmatrix} 1 \\ 2 \\ 3 \end{pmatrix}z\,\big|\, z\in\mathbb{R}\} \quad\text{and}\quad \{\begin{pmatrix} 2 \\ 4 \\ 6 \end{pmatrix}w\,\big|\, w\in\mathbb{R}\}. $$

For instance, this set contains

\begin{pmatrix} 5 \\ 10 \\ 15 \end{pmatrix} $$

(take $$z=5$$ and $$w=5/2$$) but does not contain

\begin{pmatrix} 4 \\ 8 \\ 11 \end{pmatrix} $$

(the first component gives $$z=4$$ but that clashes with the third component, similarly the first component gives $$w=4/5$$ but the third component gives something different). Here is a third description of the same set:

\{\begin{pmatrix} 3 \\ 6 \\ 9 \end{pmatrix}+\begin{pmatrix} -1 \\ -2 \\ -3 \end{pmatrix}y\,\big|\, y\in\mathbb{R}\}. $$

We need to decide when two descriptions are describing the same set. More pragmatically stated, how can a person tell when an answer to a homework question describes the same set as the one described in the back of the book?

Set Equality
Sets are equal if and only if they have the same members. A common way to show that two sets, $$S_1$$ and $$S_2$$, are equal is to show mutual inclusion: any member of $$S_1$$ is also in $$S_2$$, and any member of $$S_2$$ is also in $$S_1$$.

Exercises
/Solutions/


text:
Linear Algebra/Linear Geometry of n-Space

''For readers who have seen the elements of vectors before, in calculus or physics, this section is an optional review. However, later work will refer to this material so it is not optional if it is not a review.''

In the first section, we had to do a bit of work to show that there are only three types of solution sets— singleton, empty, and infinite. But in the special case of systems with two equations and two unknowns this is easy to see. Draw each two-unknowns equation as a line in the plane and then the two lines could have a unique intersection, be parallel, or be the same line. These pictures don't prove the results from the prior section, which apply to any number of linear equations and any number of unknowns, but nonetheless they do help us to understand those results. This section develops the ideas that we need to express our results from the prior section, and from some future sections, geometrically. In particular, while the two-dimensional case is familiar, to extend to systems with more than two unknowns we shall need some higher-dimensional geometry.


text:
Linear Algebra/Vectors in Space

"Higher-dimensional geometry" sounds exotic. It is exotic— interesting and eye-opening. But it isn't distant or unreachable.

We begin by defining one-dimensional space to be the set $$ \mathbb{R}^1 $$. To see that definition is reasonable, draw a one-dimensional space

and make the usual correspondence with $$ \mathbb{R} $$: pick a point to label $$0$$ and another to label $$1$$.

Now, with a scale and a direction, finding the point corresponding to, say $$ +2.17 $$, is easy— start at $$ 0 $$ and head in the direction of $$ 1 $$ (i.e., the positive direction), but don't stop there, go $$ 2.17 $$ times as far.

The basic idea here, combining magnitude with direction, is the key to extending to higher dimensions.

An object comprised of a magnitude and a direction is a vector (we will use the same word as in the previous section because we shall show below how to describe such an object with a column vector). We can draw a vector as having some length, and pointing somewhere.

There is a subtlety here— these vectors

are equal, even though they start in different places, because they have equal lengths and equal directions. Again: those vectors are not just alike, they are equal.

How can things that are in different places be equal? Think of a vector as representing a displacement ("vector" is Latin for "carrier" or "traveler"). These squares undergo the same displacement, despite that those displacements start in different places.

Sometimes, to emphasize this property vectors have of not being anchored, they are referred to as free vectors. Thus, these free vectors are equal as each is a displacement of one over and two up.

More generally, vectors in the plane are the same if and only if they have the same change in first components and the same change in second components: the vector extending from $$ (a_1,a_2) $$ to $$ (b_1,b_2) $$ equals the vector from $$ (c_1,c_2) $$ to $$ (d_1,d_2) $$ if and only if $$ b_1-a_1=d_1-c_1 $$ and $$ b_2-a_2=d_2-c_2 $$.

An expression like "the vector that, were it to start at $$ (a_1,a_2) $$, would extend to $$ (b_1,b_2) $$" is awkward. We instead describe such a vector as

\begin{pmatrix} b_1-a_1 \\ b_2-a_2 \end{pmatrix} $$

so that, for instance, the "one over and two up" arrows shown above picture this vector.

\begin{pmatrix} 1 \\ 2 \end{pmatrix} $$

We often draw the arrow as starting at the origin, and we then say it is in the canonical position (or natural position). When the vector

\begin{pmatrix} b_1-a_1 \\ b_2-a_2 \end{pmatrix} $$

is in its canonical position then it extends to the endpoint $$(b_1-a_1,b_2-a_2)$$.

We typically just refer to "the point

\begin{pmatrix} 1 \\ 2 \end{pmatrix} $$"

rather than "the endpoint of the canonical position of" that vector.

Thus, we will call both of these sets $$ \mathbb{R}^2 $$.

\{(x_1,x_2)\,\big|\, x_1,x_2\in\mathbb{R}\} \qquad \{\begin{pmatrix} x_1 \\ x_2 \end{pmatrix}\,\big|\, x_1,x_2\in\mathbb{R}\} $$

In the prior section we defined vectors and vector operations with an algebraic motivation;

r\cdot\begin{pmatrix} v_1 \\ v_2 \end{pmatrix} = \begin{pmatrix} rv_1 \\ rv_2 \end{pmatrix} \qquad \begin{pmatrix} v_1 \\ v_2 \end{pmatrix} + \begin{pmatrix} w_1 \\ w_2 \end{pmatrix} = \begin{pmatrix} v_1+w_1 \\ v_2+w_2 \end{pmatrix} $$

we can now interpret those operations geometrically. For instance, if $$ \vec{v} $$ represents a displacement then $$ 3\vec{v}\, $$ represents a displacement in the same direction but three times as far, and $$ -1\vec{v}\, $$ represents a displacement of the same distance as $$ \vec{v}\, $$ but in the opposite direction.

And, where $$ \vec{v} $$ and $$ \vec{w} $$ represent displacements, $$ \vec{v}+\vec{w} $$ represents those displacements combined.

The long arrow is the combined displacement in this sense: if, in one minute, a ship's motion gives it the displacement relative to the earth of $$\vec{v}$$ and a passenger's motion gives a displacement relative to the ship's deck of $$\vec{w}$$, then $$\vec{v}+\vec{w}$$ is the displacement of the passenger relative to the earth.

Another way to understand the vector sum is with the parallelogram rule. Draw the parallelogram formed by the vectors $$\vec{v}_1,\vec{v}_2$$ and then the sum $$\vec{v}_1+\vec{v}_2$$ extends along the diagonal to the far corner.

The above drawings show how vectors and vector operations behave in $$ \mathbb{R}^2 $$. We can extend to $$\mathbb{R}^3$$, or to even higher-dimensional spaces where we have no pictures, with the obvious generalization: the free vector that, if it starts at $$ (a_1,\ldots,a_n) $$, ends at $$ (b_1,\ldots,b_n) $$, is represented by this column

\begin{pmatrix} b_1-a_1 \\ \vdots \\ b_n-a_n \end{pmatrix} $$

(vectors are equal if they have the same representation), we aren't too careful to distinguish between a point and the vector whose canonical representation ends at that point,

\mathbb{R}^n= \{\begin{pmatrix} v_1 \\ \vdots \\ v_n \end{pmatrix}\,\big|\, v_1,\ldots,v_n\in\mathbb{R}\} $$

and addition and scalar multiplication are component-wise.

Having considered points, we now turn to the lines.

In $$\mathbb{R}^2$$, the line through $$ (1,2) $$ and $$ (3,1) $$ s comprised of (the endpoints of) the vectors in this set

\{ \begin{pmatrix} 1 \\ 2 \end{pmatrix}+t\cdot\begin{pmatrix} 2 \\ -1 \end{pmatrix}\,\big|\, t\in\mathbb{R}\} $$

That description expresses this picture.

The vector associated with the parameter $$t$$ has its whole body in the line— it is a direction vector for the line. Note that points on the line to the left of $$ x=1 $$ are described using negative values of $$ t $$.

In $$ \mathbb{R}^3 $$, the line through $$ (1,2,1) $$ and $$ (2,3,2) $$ is the set of (endpoints of) vectors of this form

and lines in even higher-dimensional spaces work in the same way.

If a line uses one parameter, so that there is freedom to move back and forth in one dimension, then a plane must involve two. For example, the plane through the points $$ (1,0,5) $$, $$ (2,1,-3) $$, and $$ (-2,4,0.5) $$ consists of (endpoints of) the vectors in

\{ \begin{pmatrix} 1 \\ 0 \\ 5 \end{pmatrix} +t\cdot\begin{pmatrix} 1 \\ 1 \\ -8 \end{pmatrix} +s\cdot\begin{pmatrix} -3 \\ 4 \\ -4.5 \end{pmatrix} \,\big|\, t,s\in\mathbb{R}     \} $$

(the column vectors associated with the parameters

\begin{pmatrix} 1 \\ 1 \\ -8 \end{pmatrix} = \begin{pmatrix} 2 \\ 1 \\ -3 \end{pmatrix} - \begin{pmatrix} 1 \\ 0 \\ 5 \end{pmatrix} \qquad \begin{pmatrix} -3 \\ 4 \\ -4.5 \end{pmatrix} = \begin{pmatrix} -2 \\ 4 \\ 0.5 \end{pmatrix} - \begin{pmatrix} 1 \\ 0 \\ 5 \end{pmatrix} $$

are two vectors whose whole bodies lie in the plane). As with the line, note that some points in this plane are described with negative $$t$$'s or negative $$s$$'s or both.

A description of planes that is often encountered in algebra and calculus uses a single equation as the condition that describes the relationship among the first, second, and third coordinates of points in a plane.

The translation from such a description to the vector description that we favor in this book is to think of the condition as a one-equation linear system and parametrize $$ x=(1/2)(4-y-z) $$.

Generalizing from lines and planes, we define a $$ k $$-dimensional linear surface (or $$ k $$-flat) in $$\mathbb{R}^n$$ to be $$\{\vec{p}+t_1\vec{v}_1+t_2\vec{v}_2+\cdots+t_k\vec{v}_k \,\big|\, t_1,\ldots ,t_k\in\mathbb{R}\}$$ where $$ \vec{v}_1,\ldots,\vec{v}_k\in\mathbb{R}^n $$. For example, in $$\mathbb{R}^4$$,

\{\begin{pmatrix} 2 \\ \pi \\ 3 \\ -0.5 \end{pmatrix} +t\begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \,\big|\, t\in\mathbb{R}\} $$

is a line,

\{ \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} +t\begin{pmatrix} 1 \\ 1 \\ 0 \\ -1 \end{pmatrix} +s\begin{pmatrix} 2 \\ 0 \\ 1 \\ 0 \end{pmatrix} \,\big|\, t,s\in\mathbb{R}\} $$

is a plane, and

\{ \begin{pmatrix} 3 \\ 1 \\ -2 \\ 0.5 \end{pmatrix} +r\begin{pmatrix} 0 \\ 0 \\ 0 \\ -1 \end{pmatrix} +s\begin{pmatrix} 1 \\ 0 \\ 1 \\ 0 \end{pmatrix} +t\begin{pmatrix} 2 \\ 0 \\ 1 \\ 0 \end{pmatrix} \,\big|\, r,s,t\in\mathbb{R}\} $$

is a three-dimensional linear surface. Again, the intuition is that a line permits motion in one direction, a plane permits motion in combinations of two directions, etc.

A linear surface description can be misleading about the dimension— this

L=\{ \begin{pmatrix} 1 \\ 0 \\ -1 \\ -2 \end{pmatrix} +t\begin{pmatrix} 1 \\ 1 \\ 0 \\ -1 \end{pmatrix} +s\begin{pmatrix} 2 \\ 2 \\ 0 \\ -2 \end{pmatrix} \,\big|\, t,s\in\mathbb{R}\} $$

is a degenerate plane because it is actually a line.

L=\{ \begin{pmatrix} 1 \\ 0 \\ -1 \\ -2 \end{pmatrix} +r\begin{pmatrix} 1 \\ 1 \\ 0 \\ -1 \end{pmatrix} \,\big|\, r\in\mathbb{R}\} $$

We shall see in the Linear Independence section of Chapter Two what relationships among vectors causes the linear surface they generate to be degenerate.

We finish this subsection by restating our conclusions from the first section in geometric terms. First, the solution set of a linear system with $$ n $$ unknowns is a linear surface in $$ \mathbb{R}^n $$. Specifically, it is a $$ k $$-dimensional linear surface, where $$ k $$ is the number of free variables in an echelon form version of the system. Second, the solution set of a homogeneous linear system is a linear surface passing through the origin. Finally, we can view the general solution set of any linear system as being the solution set of its associated homogeneous system offset from the origin by a vector, namely by any particular solution.

Exercises
/Solutions/

title: Linear Algebra/Vectors in Space


text:
User:Aly4halo

Photos 2 Movies --Aly4halo (talk) 18:02, 11 March 2008 (UTC)

title: User:Aly4halo


text:
Linear Algebra/Length and Angle Measures

We've translated the first section's results about solution sets into geometric terms for insight into how those sets look. But we must watch out not to be mislead by our own terms; labeling subsets of $$ \mathbb{R}^k $$ of the forms $$ \{\vec{p}+t\vec{v}\,\big|\, t\in\mathbb{R}\} $$ and $$ \{\vec{p}+t\vec{v}+s\vec{w}\,\big|\, t,s\in\mathbb{R}\} $$ as "lines" and "planes" doesn't make them act like the lines and planes of our prior experience. Rather, we must ensure that the names suit the sets. While we can't prove that the sets satisfy our intuition— we can't prove anything about intuition— in this subsection we'll observe that a result familiar from $$ \mathbb{R}^2 $$ and $$ \mathbb{R}^3 $$, when generalized to arbitrary $$ \mathbb{R}^k $$, supports the idea that a line is straight and a plane is flat. Specifically, we'll see how to do Euclidean geometry in a "plane" by giving a definition of the angle between two $$\mathbb{R}^n$$ vectors in the plane that they generate.

We can use that definition to derive a formula for the angle between two vectors. For a model of what to do, consider two vectors in $$ \mathbb{R}^3 $$. Put them in canonical position and, in the plane that they determine, consider the triangle formed by $$ \vec{u} $$, $$ \vec{v} $$, and $$ \vec{u}-\vec{v} $$. Apply the Law of Cosines, $$|\vec{u}-\vec{v}\,|^2 = 2\,|\vec{u}\,|\,|\vec{v}\,|\cos\theta$$, where $$ \theta $$ is the angle between the vectors. Expand both sides
 * \vec{u}\,|^2+|\vec{v}\,|^2-

(u_1-v_1)^2+(u_2-v_2)^2+(u_3-v_3)^2$$
 * $$=(u_1^2+u_2^2+u_3^2)+(v_1^2+v_2^2+v_3^2)-

2\,|\vec{u}\,|\,|\vec{v}\,|\cos\theta $$

and simplify.

\theta = \arccos(\,\frac{u_1v_1+u_2v_2+u_3v_3}{ $$
 * \vec{u}\,|\,|\vec{v}\,| }\,)

In higher dimensions no picture suffices but we can make the same argument analytically. First, the form of the numerator is clear— it comes from the middle terms of the squares $$ (u_1-v_1)^2 $$, $$ (u_2-v_2)^2 $$, etc.

Note that the dot product of two vectors is a real number, not a vector, and that the dot product of a vector from $$ \mathbb{R}^n $$ with a vector from $$ \mathbb{R}^m $$ is defined only when $$ n $$ equals $$ m $$. Note also this relationship between dot product and length: dotting a vector with itself gives its length squared $$ \vec{u}\cdot\vec{u}=u_1u_1+\cdots+u_nu_n=|\vec{u}\,|^2 $$.

Still reasoning with letters, but guided by the pictures, we use the next theorem to argue that the triangle formed by $$ \vec{u} $$, $$ \vec{v} $$, and $$ \vec{u}-\vec{v} $$ in $$ \mathbb{R}^n $$ lies in the planar subset of $$ \mathbb{R}^n $$ generated by $$ \vec{u} $$ and $$ \vec{v} $$.

This inequality is the source of the familiar saying, "The shortest distance between two points is in a straight line."

This result supports the intuition that even in higher-dimensional spaces, lines are straight and planes are flat. For any two points in a linear surface, the line segment connecting them is contained in that surface (this is easily checked from the definition). But if the surface has a bend then that would allow for a shortcut (shown here grayed, while the segment from $$P$$ to $$Q$$ that is contained in the surface is solid). Because the Triangle Inequality says that in any $$\mathbb{R}^n$$, the shortest cut between two endpoints is simply the line segment connecting them, linear surfaces have no such bends.

Back to the definition of angle measure. The heart of the Triangle Inequality's proof is the "$$ \vec{u}\cdot\vec{v}\leq |\vec{u}\,|\,|\vec{v}\,| $$" line. At first glance, a reader might wonder if some pairs of vectors satisfy the inequality in this way: while $$ \vec{u}\cdot\vec{v} $$ is a large number, with absolute value bigger than the right-hand side, it is a negative large number. The next result says that no such pair of vectors exists.

The Cauchy-Schwarz inequality assures us that the next definition makes sense because the fraction has absolute value less than or equal to one.

Thus vectors from $$ \mathbb{R}^n $$ are orthogonal (or perpendicular) if and only if their dot product is zero.

Exercises
/Solutions/


text:
Linear Algebra/Reduced Echelon Form

After developing the mechanics of Gauss' method, we observed that it can be done in more than one way. One example is that we sometimes have to swap rows and there can be more than one row to choose from. Another example is that from this matrix

\begin{pmatrix} 2 &2 \\ 4 &3 \end{pmatrix} $$

Gauss' method could derive any of these echelon form matrices.

\begin{pmatrix} 2 &2 \\ 0 &-1 \end{pmatrix} \qquad \begin{pmatrix} 1 &1 \\ 0 &-1 \end{pmatrix} \qquad \begin{pmatrix} 2 &0 \\ 0 &-1 \end{pmatrix} $$

The first results from $$-2\rho_1+\rho_2$$. The second comes from following $$(1/2)\rho_1$$ with $$-4\rho_1+\rho_2$$. The third comes from $$-2\rho_1+\rho_2$$ followed by $$2\rho_2+\rho_1$$ (after the first pivot the matrix is already in echelon form so the second one is extra work but it is nonetheless a legal row operation).

The fact that the echelon form outcome of Gauss' method is not unique leaves us with some questions. Will any two echelon form versions of a system have the same number of free variables? Will they in fact have exactly the same variables free? In this section we will answer both questions "yes". We will do more than answer the questions. We will give a way to decide if one linear system can be derived from another by row operations. The answers to the two questions will follow from this larger result.

title: Linear Algebra/Reduced Echelon Form


text:
Linear Algebra/Gauss-Jordan Reduction

Gaussian elimination coupled with back-substitution solves linear systems, but it's not the only method possible. Here is an extension of Gauss' method that has some advantages.

Note that the pivot operations in the first stage proceed from column one to column three while the pivot operations in the third stage proceed from column three to column one.

This extension of Gauss' method is Gauss-Jordan reduction. It goes past echelon form to a more refined, more specialized, matrix form.

The disadvantage of using Gauss-Jordan reduction to solve a system is that the additional row operations mean additional arithmetic. The advantage is that the solution set can just be read off.

In any echelon form, plain or reduced, we can read off when a system has an empty solution set because there is a contradictory equation, we can read off when a system has a one-element solution set because there is no contradiction and every variable is the leading variable in some row, and we can read off when a system has an infinite solution set because there is no contradiction and at least one variable is free.

In reduced echelon form we can read off not just what kind of solution set the system has, but also its description. Whether or not the echelon form is reduced, we have no trouble describing the solution set when it is empty, of course. The two examples above show that when the system has a single solution then the solution can be read off from the right-hand column. In the case when the solution set is infinite, its parametrization can also be read off of the reduced echelon form. Consider, for example, this system that is shown brought to echelon form and then to reduced echelon form.

\left(\begin{array}{cccc|c} 2 &6  &1  &2  &5  \\ 0  &3  &1  &4  &1  \\ 0  &3  &1  &2  &5 \end{array}\right) \xrightarrow[]{-\rho_2+\rho_3} \left(\begin{array}{cccc|c} 2 &6  &1  &2  &5  \\ 0  &3  &1  &4  &1  \\ 0  &0  &0  &-2 &4 \end{array}\right)$$
 * $$\xrightarrow[\begin{array}{c}\\[-19pt]\scriptstyle (1/3)\rho_2 \\[-5pt]\scriptstyle -(1/2)\rho_3\end{array}]{(1/2)\rho_1}

\;\xrightarrow[-\rho_3+\rho_1]{(4/3)\rho_3+\rho_2} \;\xrightarrow[]{-3\rho_2+\rho_1} \left(\begin{array}{cccc|c} 1 &0  &-1/2  &0  &-9/2  \\ 0  &1  &1/3   &0  &3  \\ 0  &0  &0     &1  &-2 \end{array}\right) $$

Starting with the middle matrix, the echelon form version, back substitution produces $$-2x_4=4$$ so that $$x_4=-2$$, then another back substitution gives $$3x_2+x_3+4(-2)=1$$ implying that $$x_2=3-(1/3)x_3$$, and then the final back substitution gives $$2x_1+6(3-(1/3)x_3)+x_3+2(-2)=5$$ implying that $$x_1=-(9/2)+(1/2)x_3$$. Thus the solution set is this.

S=\{\begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} =\begin{pmatrix} -9/2 \\ 3 \\ 0 \\ -2 \end{pmatrix} +\begin{pmatrix} 1/2 \\ -1/3 \\ 1 \\ 0 \end{pmatrix}x_3 \,\big|\, x_3\in\mathbb{R}\} $$

Now, considering the final matrix, the reduced echelon form version, note that adjusting the parametrization by moving the $$x_3$$ terms to the other side does indeed give the description of this infinite solution set.

Part of the reason that this works is straightforward. While a set can have many parametrizations that describe it, e.g., both of these also describe the above set $$S$$ (take $$t$$ to be $$x_3/6$$ and $$s$$ to be $$x_3-1$$)

\{\begin{pmatrix} -9/2 \\ 3 \\ 0 \\ -2 \end{pmatrix} +\begin{pmatrix} 3 \\ -2 \\ 6 \\ 0 \end{pmatrix}t \,\big|\, t\in\mathbb{R}\} \qquad \{\begin{pmatrix} -4 \\ 8/3 \\ 1 \\ -2 \end{pmatrix} +\begin{pmatrix} 1/2 \\ -1/3 \\ 1 \\ 0 \end{pmatrix}s \,\big|\, s\in\mathbb{R}\} $$

nonetheless we have in this book stuck to a convention of parametrizing using the unmodified free variables (that is, $$x_3=x_3$$ instead of $$x_3=6t$$). We can easily see that a reduced echelon form version of a system is equivalent to a parametrization in terms of unmodified free variables. For instance,

 * $$\begin{array}{rl}

x_1 &=4-2x_3 \\ x_2 &=3-x_3 \end{array} \quad\Longleftrightarrow\quad \left(\begin{array}{ccc|c} 1 &0  &2  &4  \\ 0  &1  &1  &3  \\ 0  &0  &0  &0 \end{array}\right) $$

(to move from left to right we also need to know how many equations are in the system). So, the convention of parametrizing with the free variables by solving each equation for its leading variable and then eliminating that leading variable from every other equation is exactly equivalent to the reduced echelon form conditions that each leading entry must be a one and must be the only nonzero entry in its column.

Not as straightforward is the other part of the reason that the reduced echelon form version allows us to read off the parametrization that we would have gotten had we stopped at echelon form and then done back substitution. The prior paragraph shows that reduced echelon form corresponds to some parametrization, but why the same parametrization? A solution set can be parametrized in many ways, and Gauss' method or the Gauss-Jordan method can be done in many ways, so a first guess might be that we could derive many different reduced echelon form versions of the same starting system and many different parametrizations. But we never do. Experience shows that starting with the same system and proceeding with row operations in many different ways always yields the same reduced echelon form and the same parametrization (using the unmodified free variables).

In the rest of this section we will show that the reduced echelon form version of a matrix is unique. It follows that the parametrization of a linear system in terms of its unmodified free variables is unique because two different ones would give two different reduced echelon forms.

We shall use this result, and the ones that lead up to it, in the rest of the book but perhaps a restatement in a way that makes it seem more immediately useful may be encouraging. Imagine that we solve a linear system, parametrize, and check in the back of the book for the answer. But the parametrization there appears different. Have we made a mistake, or could these be different-looking descriptions of the same set, as with the three descriptions above of $$S$$? The prior paragraph notes that we will show here that different-looking parametrizations (using the unmodified free variables) describe genuinely different sets.

Here is an informal argument that the reduced echelon form version of a matrix is unique. Consider again the example that started this section of a matrix that reduces to three different echelon form matrices. The first matrix of the three is the natural echelon form version. The second matrix is the same as the first except that a row has been halved. The third matrix, too, is just a cosmetic variant of the first. The definition of reduced echelon form outlaws this kind of fooling around. In reduced echelon form, halving a row is not possible because that would change the row's leading entry away from one, and neither is combining rows possible, because then a leading entry would no longer be alone in its column.

This informal justification is not a proof; we have argued that no two different reduced echelon form matrices are related by a single row operation step, but we have not ruled out the possibility that multiple steps might do. Before we go to that proof, we finish this subsection by rephrasing our work in a terminology that will be enlightening.

Many different matrices yield the same reduced echelon form matrix. The three echelon form matrices from the start of this section, and the matrix they were derived from, all give this reduced echelon form matrix.

\begin{pmatrix} 1 &0  \\ 0  &1 \end{pmatrix} $$

We think of these matrices as related to each other. The next result speaks to this relationship.

This lemma suggests that "reduces to" is misleading— where $$ A\longrightarrow B $$, we shouldn't think of $$ B $$ as "after" $$ A $$ or "simpler than" $$A$$. Instead we should think of them as interreducible or interrelated. Below is a picture of the idea. The matrices from the start of this section and their reduced echelon form version are shown in a cluster. They are all interreducible; these relationships are shown also. We say that matrices that reduce to each other are "equivalent with respect to the relationship of row reducibility". The next result verifies this statement using the definition of an equivalence.

The diagram below shows the collection of all matrices as a box. Inside that box, each matrix lies in some class. Matrices are in the same class if and only if they are interreducible. The classes are disjoint— no matrix is in two distinct classes. The collection of matrices has been partitioned into row equivalence classes.

One of the classes in this partition is the cluster of matrices shown above, expanded to include all of the nonsingular $$2 \! \times \! 2$$ matrices.

The next subsection proves that the reduced echelon form of a matrix is unique; that every matrix reduces to one and only one reduced echelon form matrix. Rephrased in terms of the row-equivalence relationship, we shall prove that every matrix is row equivalent to one and only one reduced echelon form matrix. In terms of the partition what we shall prove is: every equivalence class contains one and only one reduced echelon form matrix. So each reduced echelon form matrix serves as a representative of its class.

After that proof we shall, as mentioned in the introduction to this section, have a way to decide if one matrix can be derived from another by row reduction. We just apply the Gauss-Jordan procedure to both and see whether or not they come to the same reduced echelon form.

Exercises
/Solutions/

title: Linear Algebra/Gauss-Jordan Reduction


text:
Linear Algebra/Row Equivalence

We will close this section and this chapter by proving that every matrix is row equivalent to one and only one reduced echelon form matrix. The ideas that appear here will reappear, and be further developed, in the next chapter.

The underlying theme here is that one way to understand a mathematical situation is by being able to classify the cases that can happen. We have met this theme several times already. We have classified solution sets of linear systems into the no-elements, one-element, and infinitely-many elements cases. We have also classified linear systems with the same number of equations as unknowns into the nonsingular and singular cases. We adopted these classifications because they give us a way to understand the situations that we were investigating. Here, where we are investigating row equivalence, we know that the set of all matrices breaks into the row equivalence classes. When we finish the proof here, we will have a way to understand each of those classes— its matrices can be thought of as derived by row operations from the unique reduced echelon form matrix in that class.

To understand how row operations act to transform one matrix into another, we consider the effect that they have on the parts of a matrix. The crucial observation is that row operations combine the rows linearly.

(We have already used the phrase "linear combination" in this book. The meaning is unchanged, but the next result's statement makes a more formal definition in order.)

In this subsection we will use the convention that, where a matrix is named with an upper case roman letter, the matching lower-case greek letter names the rows.

A= \begin{pmatrix} \cdots \alpha_1 \cdots \\ \cdots \alpha_2 \cdots \\ \vdots                \\ \cdots \alpha_m \cdots \end{pmatrix} \qquad B= \begin{pmatrix} \cdots \beta_1 \cdots \\ \cdots \beta_2 \cdots \\ \vdots               \\ \cdots \beta_m\cdots \end{pmatrix} $$

The proof below uses induction on the number of row operations used to reduce one matrix to the other. Before we proceed, here is an outline of the argument (readers unfamiliar with induction may want to compare this argument with the one used in the "$$\text{General}=\text{Particular}+\text{Homogeneous}$$" proof). First, for the base step of the argument, we will verify that the proposition is true when reduction can be done in zero row operations. Second, for the inductive step, we will argue that if being able to reduce the first matrix to the second in some number $$t\geq 0$$ of operations implies that each row of the second is a linear combination of the rows of the first, then being able to reduce the first to the second in $$t+1$$ operations implies the same thing. Together, this base step and induction step prove this result because by the base step the proposition is true in the zero operations case, and by the inductive step the fact that it is true in the zero operations case implies that it is true in the one operation case, and the inductive step applied again gives that it is therefore true in the two operations case, etc.

The prior result gives us the insight that Gauss' method works by taking linear combinations of the rows. But to what end; why do we go to echelon form as a particularly simple, or basic, version of a linear system? The answer, of course, is that echelon form is suitable for back substitution, because we have isolated the variables. For instance, in this matrix

R=\begin{pmatrix} 2 &3  &7  &8  &0  &0  \\ 0  &0  &1  &5  &1  &1  \\ 0  &0  &0  &3  &3  &0  \\ 0  &0  &0  &0  &2  &1 \end{pmatrix} $$

$$x_1$$ has been removed from $$x_5$$'s equation. That is, Gauss' method has made $$x_5$$'s row independent of $$x_1$$'s row.

Independence of a collection of row vectors, or of any kind of vectors, will be precisely defined and explored in the next chapter. But a first take on it is that we can show that, say, the third row above is not comprised of the other rows, that $$\rho_3\neq c_1\rho_1+c_2\rho_2+c_4\rho_4$$. For, suppose that there are scalars $$c_1$$, $$c_2$$, and $$c_4$$ such that this relationship holds.

 * $$\begin{array}{rl}

\begin{pmatrix} 0 &0  &0  &3  &3  &0 \end{pmatrix} &=c_1\begin{pmatrix} 2 &3 &7 &8 &0 &0 \end{pmatrix}            \\ &\quad+c_2\begin{pmatrix} 0 &0 &1 &5 &1 &1 \end{pmatrix} \\ &\quad+c_4\begin{pmatrix} 0 &0 &0 &0 &2 &1 \end{pmatrix} \end{array}$$

The first row's leading entry is in the first column and narrowing our consideration of the above relationship to consideration only of the entries from the first column $$0=2c_1+0c_2+0c_4$$ gives that $$c_1=0$$. The second row's leading entry is in the third column and the equation of entries in that column $$0=7c_1+1c_2+0c_4$$, along with the knowledge that $$c_1=0$$, gives that $$c_2=0$$. Now, to finish, the third row's leading entry is in the fourth column and the equation of entries in that column $$3=8c_1+5c_2+0c_4$$, along with $$c_1=0$$ and $$c_2=0$$, gives an impossibility.

The following result shows that this effect always holds. It shows that what Gauss' linear elimination method eliminates is linear relationships among the rows.

We can now prove that each matrix is row equivalent to one and only one reduced echelon form matrix. We will find it convenient to break the first half of the argument off as a preliminary lemma. For one thing, it holds for any echelon form whatever, not just reduced echelon form.

For the proof we rephrase the result in more technical terms. Define the form of an $$m \! \times \! n$$ matrix to be the sequence $$\langle \ell_1,\ell_2,\ldots\,,\ell_m \rangle$$ where $$\ell_i$$ is the column number of the leading entry in row $$i$$ and $$\ell_i=\infty$$ if there is no leading entry in that row. The lemma says that if two echelon form matrices are row equivalent then their forms are equal sequences.

That lemma answers two of the questions that we have posed: (i) any two echelon form versions of a matrix have the same free variables, and consequently, and (ii) any two echelon form versions have the same number of free variables. There is no linear system and no combination of row operations such that, say, we could solve the system one way and get $$y$$ and $$z$$ free but solve it another way and get $$y$$ and $$w$$ free, or solve it one way and get two free variables while solving it another way yields three.

We finish now by specializing to the case of reduced echelon form matrices.

We end with a recap. In Gauss' method we start with a matrix and then derive a sequence of other matrices. We defined two matrices to be related if one can be derived from the other. That relation is an equivalence relation, called row equivalence, and so partitions the set of all matrices into row equivalence classes. (There are infinitely many matrices in the pictured class, but we've only got room to show two.) We have proved there is one and only one reduced echelon form matrix in each row equivalence class. So the reduced echelon form is a canonical form for row equivalence: the reduced echelon form matrices are representatives of the classes. We can answer questions about the classes by translating them into questions about the representatives.

Exercises
/Solutions/

title: Linear Algebra/Row Equivalence


text:
Linear Algebra/Automation

This is a PASCAL routine to do $$ k\rho_i+\rho_j $$ to an augmented matrix.

Of course this is only one part of a whole program, but it makes the point that Gaussian reduction is ideal for computer coding.

There are pitfalls, however. For example, some arise from the computer's use of finite-precision approximations of real numbers.

These systems provide a simple example. (The second two lines are hard to tell apart.) Both have $$ (1,1) $$ as their unique solution.

In the first system, some small change in the numbers will produce only a small change in the solution:

\begin{array}{*{2}{rc}r} x &+  &2y &= &3                  \\ 3x &- &2y &= &1.008 \end{array} $$

gives a solution of $$ (1.002,0.999) $$. Geometrically, changing one of the lines by a small amount does not change the intersection point by very much.

That's not true for the second system. A small change in the coefficients

\begin{array}{*{2}{rc}r} x             &+ &2y  &=  &3                  \\ 1.000\,000\,01x &+ &2y &=  &3.000\,000\,03 \end{array} $$

leads to a completely different answer: $$ (3,0) $$.

The solution of the second example varies wildly, depending on a $$ 9 $$-th digit. That's bad news for a machine using $$ 8 $$ digits to represent reals. In short, systems that are nearly singular may be hard to compute with.

Another thing that can go wrong is error propagation. In a system with a large number of equations (say, 100 or more), small rounding errors early in the procedure can snowball to overwhelm the solution at the end.

These issues, and many others like them, are outside the scope of this book, but remember that just because Gauss' method always works in theory and just because a program correctly implements that method and just because the answer appears on green-bar paper, doesn't mean that answer is right. In practice, always use a package where experts have worked hard to counter what can go wrong.

title: Linear Algebra/Automation


text:
Linear Algebra/Topic: Computer Algebra Systems

The linear systems in this chapter are small enough that their solution by hand is easy. But large systems are easiest, and safest, to do on a computer. There are special purpose programs such as LINPACK for this job. Another popular tool is a general purpose computer algebra system, including both commercial packages such as Maple, Mathematica, or MATLAB, or free packages such as SciLab, Sage, or Octave.

For example, in the Topic on Networks, we need to solve this.

\begin{array}{*{7}{rc}r} i_0 &-  &i_1  &-  &i_2  &   &    &  &    &   &    &  &    &=  &0  \\ &  &i_1  &   &     &-  &i_3 &  &    &-  &i_5 &  &    &=  &0  \\ &  &     &   &i_2  &   &    &- &i_4 &+  &i_5 &  &    &=  &0  \\ &  &     &   &     &   &i_3 &+ &i_4 &   &    &- &i_6 &=  &0  \\ &  &5i_1 &   &     &+  &10i_3  &  & &   &    &  &    &=  &10  \\ &  &     &   &2i_2 &   &    &+ &4i_4 &  &    &  &    &=  &10  \\ &  &5i_1 &-  &2i_2 &   &    &  &    &+  &50i_5 &&    &=  &0 \end{array} $$

It can be done by hand, but it would take a while and be error-prone. Using a computer is better.

We illustrate by solving that system under Maple (for another system, a user's manual would obviously detail the exact syntax needed). The array of coefficients can be entered in this way

> A:=array( 1,-1,-1,0,0,0,0], [0,1,0,-1,0,-1,0], [0,0,1,0,-1,1,0], [0,0,0,1,1,0,-1], [0,5,0,10,0,0,0], [0,0,2,0,4,0,0], [0,5,-2,0,0,50,0 );

(putting the rows on separate lines is not necessary, but is done for clarity). The vector of constants is entered similarly.

> u:=array( [0,0,0,0,10,10,0] );

Then the system is solved, like magic.

> linsolve(A,u); 7 2  5  2  5     7 [ -, -, -, -, -, 0, - ] 3  3  3  3  3     3

Mathematica can solve this with This returns the following output: Systems with infinitely many solutions are solved in the same way— the computer simply returns a parametrization.

Exercises
''Answers for this Topic use Maple as the computer algebra system. In particular, all of these were tested on Maple V running under MS-DOS NT version 4.0. (On all of them, the preliminary command to load the linear algebra package along with Maple's responses to the Enter key, have been omitted.) Other systems have similar commands.''

/Solutions/


text:
Linear Algebra/Topic: Input-Output Analysis

An economy is an immensely complicated network of interdependences. Changes in one part can ripple out to affect other parts. Economists have struggled to be able to describe, and to make predictions about, such a complicated object. Mathematical models using systems of linear equations have emerged as a key tool. One is Input-Output Analysis, pioneered by W. Leontief, who won the 1973 Nobel Prize in Economics.

Consider an economy with many parts, two of which are the steel industry and the auto industry. As they work to meet the demand for their product from other parts of the economy, that is, from users external to the steel and auto sectors, these two interact tightly. For instance, should the external demand for autos go up, that would lead to an increase in the auto industry's usage of steel. Or, should the external demand for steel fall, then it would lead to a fall in steel's purchase of autos. The type of Input-Output model we will consider takes in the external demands and then predicts how the two interact to meet those demands.

We start with a listing of production and consumption statistics. (These numbers, giving dollar values in millions, are excerpted from, describing the 1958 U.S. economy. Today's statistics would be quite different, both because of inflation and because of technical changes in the industries.)

For instance, the dollar value of steel used by the auto industry in this year is $$2,664$$ million. Note that industries may consume some of their own output.

We can fill in the blanks for the external demand. This year's value of the steel used by others this year is $$17,389$$ and this year's value of the auto used by others is $$21,268$$. With that, we have a complete description of the external demands and of how auto and steel interact, this year, to meet them.

Now, imagine that the external demand for steel has recently been going up by $$200$$ per year and so we estimate that next year it will be $$17,589$$. Imagine also that for similar reasons we estimate that next year's external demand for autos will be down $$25$$ to $$21,243$$. We wish to predict next year's total outputs.

That prediction isn't as simple as adding $$200$$ to this year's steel total and subtracting $$25$$ from this year's auto total. For one thing, a rise in steel will cause that industry to have an increased demand for autos, which will mitigate, to some extent, the loss in external demand for autos. On the other hand, the drop in external demand for autos will cause the auto industry to use less steel, and so lessen somewhat the upswing in steel's business. In short, these two industries form a system, and we need to predict the totals at which the system as a whole will settle.

For that prediction, let $$s$$ be next years total production of steel and let $$a$$ be next year's total output of autos. We form these equations.

 * $$\begin{array}{rl}

\text{next year}\textrm{'}\text{s production of steel} &=\text{next year}\textrm{'}\text{s use of steel by steel}  \\ &\quad+\text{next year}\textrm{'}\text{s use of steel by auto} \\ &\quad+\text{next year}\textrm{'}\text{s use of steel by others} \\ \text{next year}\textrm{'}\text{s production of autos} &=\text{next year}\textrm{'}\text{s use of autos by steel}  \\ &\quad+\text{next year}\textrm{'}\text{s use of autos by auto} \\ &\quad+\text{next year}\textrm{'}\text{s use of autos by others} \end{array}$$

On the left side of those equations go the unknowns $$s$$ and $$a$$. At the ends of the right sides go our external demand estimates for next year $$17,589$$ and $$21,243$$. For the remaining four terms, we look to the table of this year's information about how the industries interact.

For instance, for next year's use of steel by steel, we note that this year the steel industry used $$5395$$ units of steel input to produce $$25,448$$ units of steel output. So next year, when the steel industry will produce $$s$$ units out, we expect that doing so will take $$s\cdot (5395)/(25\,448)$$ units of steel input— this is simply the assumption that input is proportional to output. (We are assuming that the ratio of input to output remains constant over time; in practice, models may try to take account of trends of change in the ratios.)

Next year's use of steel by the auto industry is similar. This year, the auto industry uses $$2664$$ units of steel input to produce $$30346$$ units of auto output. So next year, when the auto industry's total output is $$a$$, we expect it to consume $$a\cdot (2664)/(30346)$$ units of steel.

Filling in the other equation in the same way, we get this system of linear equation.

\begin{array}{*{3}{rc}r} {\displaystyle\frac{5\,395}{25\,448}}\cdot s &+ &{\displaystyle\frac{2\,664}{30\,346}}\cdot a &+ &17\,589 &= &s \\[1em] {\displaystyle\frac{48}{25\,448}}\cdot s    &+ &{\displaystyle\frac{9\,030}{30\,346}}\cdot a &+ &21\,243 &= &a \end{array} $$

Gauss' method on this system.

\begin{array}{*{2}{rc}r} (20\,053/25\,448)s &- &(2\,664/30\,346)a &= &17\,589 \\ -(48/25\,448)s     &+ &(21\,316/30\,346)a &= &21\,243 \end{array} $$

gives $$s=25\,698$$ and $$a=30\,311$$.

Looking back, recall that above we described why the prediction of next year's totals isn't as simple as adding $$200$$ to last year's steel total and subtracting $$25$$ from last year's auto total. In fact, comparing these totals for next year to the ones given at the start for the current year shows that, despite the drop in external demand, the total production of the auto industry is predicted to rise. The increase in internal demand for autos caused by steel's sharp rise in business more than makes up for the loss in external demand for autos.

One of the advantages of having a mathematical model is that we can ask "What if ...?" questions. For instance, we can ask "What if the estimates for next year's external demands are somewhat off?" To try to understand how much the model's predictions change in reaction to changes in our estimates, we can try revising our estimate of next year's external steel demand from $$17,589$$ down to $$17,489$$, while keeping the assumption of next year's external demand for autos fixed at $$21,243$$. The resulting system

\begin{array}{*{2}{rc}r} (20\,053/25\,448)s &- &(2\,664/30\,346)a &= &17\,489 \\ -(48/25\,448)s     &+ &(21\,316/30\,346)a &= &21\,243 \end{array} $$

when solved gives $$s=25\,571$$ and $$a=30\,311$$. This kind of exploration of the model is sensitivity analysis. We are seeing how sensitive the predictions of our model are to the accuracy of the assumptions.

Obviously, we can consider larger models that detail the interactions among more sectors of an economy. These models are typically solved on a computer, using the techniques of matrix algebra that we will develop in Chapter Three. Some examples are given in the exercises. Obviously also, a single model does not suit every case; expert judgment is needed to see if the assumptions underlying the model are reasonable for a particular case. With those caveats, however, this model has proven in practice to be a useful and accurate tool for economic analysis. For further reading, try and.

Exercises
Hint: these systems are easiest to solve on a computer.

/Solutions/


text:
Linear Algebra/Topic: Accuracy of Computations

Gauss' method lends itself nicely to computerization. The code below illustrates. It operates on an $$n \! \times \! n$$ matrix a, pivoting with the first row, then with the second row, etc.

(This code is in the C language. Here is a brief translation. The loop construct for (pivot_row = 1; pivot_row <= n - 1; pivot_row++) { ... } sets pivot_row to 1 and then iterates while pivot_row is less than or equal to $$n-1$$, each time through incrementing pivot_row by one with the "++" operation. The other non-obvious construct is that the "-=" in the innermost loop amounts to the a[row_below, col] =- multiplier * a[pivot_row, col] + a[row_below, col]} operation.)

While this code provides a quick take on how Gauss' method can be mechanized, it is not ready to use. It is naive in many ways. The most glaring way is that it assumes that a nonzero number is always found in the <tt>pivot_row, pivot_row</tt> position for use as the pivot entry. To make it practical, one way in which this code needs to be reworked is to cover the case where finding a zero in that location leads to a row swap, or to the conclusion that the matrix is singular.

Adding some <tt>if</tt>$$\cdots$$ statements to cover those cases is not hard, but we will instead consider some more subtle ways in which the code is naive. There are pitfalls arising from the computer's reliance on finite-precision floating point arithmetic.

For example, we have seen above that we must handle as a separate case a system that is singular. But systems that are nearly singular also require care. Consider this one.

\begin{array}{*{2}{rc}r} x &+ &2y &= &3 \\ 1.000\,000\,01x &+ &2y &= &3.000\,000\,01 \end{array} $$

By eye we get the solution $$x=1$$ and $$y=1$$. But a computer has more trouble. A computer that represents real numbers to eight significant places (as is common, usually called single precision) will represent the second equation internally as $$1.000\,000\,0x+2y=3.000\,000\,0$$, losing the digits in the ninth place. Instead of reporting the correct solution, this computer will report something that is not even close— this computer thinks that the system is singular because the two equations are represented internally as equal.

For some intuition about how the computer could come up with something that far off, we can graph the system. At the scale of this graph, the two lines cannot be resolved apart. This system is nearly singular in the sense that the two lines are nearly the same line. Near-singularity gives this system the property that a small change in the system can cause a large change in its solution; for instance, changing the $$3.000\,000\,01$$ to $$3.000\,000\,03$$ changes the intersection point from $$(1,1)$$ to $$(3,0)$$. This system changes radically depending on a ninth digit, which explains why the eight-place computer has trouble. A problem that is very sensitive to inaccuracy or uncertainties in the input values is ill-conditioned.

The above example gives one way in which a system can be difficult to solve on a computer. It has the advantage that the picture of nearly-equal lines gives a memorable insight into one way that numerical difficulties can arise. Unfortunately this insight isn't very useful when we wish to solve some large system. We cannot, typically, hope to understand the geometry of an arbitrary large system. In addition, there are ways that a computer's results may be unreliable other than that the angle between some of the linear surfaces is quite small.

For an example, consider the system below, from.

\begin{array}{*{2}{rc}r} 0.001x &+  &y  &=  &1  \\ x &-  &y  &=  &0 \end{array} \qquad(*)$$

The second equation gives $$x=y$$, so $$x=y=1/1.001$$ and thus both variables have values that are just less than $$1$$. A computer using two digits represents the system internally in this way (we will do this example in two-digit floating point arithmetic, but a similar one with eight digits is easy to invent).

\begin{array}{*{2}{rc}r} (1.0\times 10^{-3})x &+  &(1.0\times 10^{0})y  &=  &1.0\times 10^{0}  \\ (1.0\times 10^{0})x  &-  &(1.0\times 10^{0})y  &=  &0.0\times 10^{0} \end{array} $$

The computer's row reduction step $$-1000\rho_1+\rho_2$$ produces a second equation $$-1001y=-999$$, which the computer rounds to two places as $$(-1.0\times 10^{3})y=-1.0\times 10^{3}$$. Then the computer decides from the second equation that $$y=1$$ and from the first equation that $$x=0$$. This $$y$$ value is fairly good, but the $$x$$ is quite bad. Thus, another cause of unreliable output is a mixture of floating point arithmetic and a reliance on pivots that are small.

An experienced programmer may respond that we should go to double precision where sixteen significant digits are retained. This will indeed solve many problems. However, there are some difficulties with it as a general approach. For one thing, double precision takes longer than single precision (on a '486 chip, multiplication takes eleven ticks in single precision but fourteen in double precision ) and has twice the memory requirements. So attempting to do all calculations in double precision is just not practical. And besides, the above systems can obviously be tweaked to give the same trouble in the seventeenth digit, so double precision won't fix all problems. What we need is a strategy to minimize the numerical trouble arising from solving systems on a computer, and some guidance as to how far the reported solutions can be trusted.

Mathematicians have made a careful study of how to get the most reliable results. A basic improvement on the naive code above is to not simply take the entry in the pivot_row, pivot_row position for the pivot, but rather to look at all of the entries in the pivot_row column below the pivot_row row, and take the one that is most likely to give reliable results (e.g., take one that is not too small). This strategy is partial pivoting. For example, to solve the troublesome system ($$*$$) above, we start by looking at both equations for a best first pivot, and taking the $$1$$ in the second equation as more likely to give good results. Then, the pivot step of $$-.001\rho_2+\rho_1$$ gives a first equation of $$1.001y=1$$, which the computer will represent as $$(1.0\times 10^{0})y=1.0\times 10^{0}$$, leading to the conclusion that $$y=1$$ and, after back-substitution, $$x=1$$, both of which are close to right. The code from above can be adapted to this purpose.

A full analysis of the best way to implement Gauss' method is outside the scope of the book (see ), but the method recommended by most experts is a variation on the code above that first finds the best pivot among the candidates, and then scales it to a number that is less likely to give trouble. This is scaled partial pivoting.

In addition to returning a result that is likely to be reliable, most well-done code will return a number, called the condition number that describes the factor by which uncertainties in the input numbers could be magnified to become inaccuracies in the results returned (see ).

The lesson of this discussion is that just because Gauss' method always works in theory, and just because computer code correctly implements that method, and just because the answer appears on green-bar paper, doesn't mean that the answer is reliable. In practice, always use a package where experts have worked hard to counter what can go wrong.

Exercises
/Solutions/


text:
Linear Algebra/Topic: Analyzing Networks

The diagram below shows some of a car's electrical network. The battery is on the left, drawn as stacked line segments. The wires are drawn as lines, shown straight and with sharp right angles for neatness. Each light is a circle enclosing a loop. The designer of such a network needs to answer questions like: How much electricity flows when both the hi-beam headlights and the brake lights are on? Below, we will use linear systems to analyze simpler versions of electrical networks.

For the analysis we need two facts about electricity and two facts about electrical networks.

The first fact about electricity is that a battery is like a pump: it provides a force impelling the electricity to flow through the circuits connecting the battery's ends, if there are any such circuits. We say that the battery provides a potential to flow. Of course, this network accomplishes its function when, as the electricity flows through a circuit, it goes through a light. For instance, when the driver steps on the brake then the switch makes contact and a circuit is formed on the left side of the diagram, and the electrical current flowing through that circuit will make the brake lights go on, warning drivers behind.

The second electrical fact is that in some kinds of network components the amount of flow is proportional to the force provided by the battery. That is, for each such component there is a number, its resistance, such that the potential is equal to the flow times the resistance. The units of measurement are: potential is described in volts, the rate of flow is in amperes, and resistance to the flow is in ohms. These units are defined so that $$\mbox{volts}=\mbox{amperes}\cdot\mbox{ohms}$$.

Components with this property, that the voltage-amperage response curve is a line through the origin, are called resistors. (Light bulbs such as the ones shown above are not this kind of component, because their ohmage changes as they heat up.) For example, if a resistor measures $$2$$ ohms then wiring it to a $$12$$ volt battery results in a flow of $$6$$ amperes. Conversely, if we have electrical current of $$2$$ amperes through it then there must be a $$4$$ volt potential difference between its ends. This is the voltage drop across the resistor. One way to think of a electrical circuits like the one above is that the battery provides a voltage rise while the other components are voltage drops.

The two facts that we need about networks are Kirchhoff's Laws.
 * Current Law. For any point in a network, the flow in equals the flow out.
 * Voltage Law. Around any circuit the total drop equals the total rise.

In the above network there is only one voltage rise, at the battery, but some networks have more than one.

For a start we can consider the network below. It has a battery that provides the potential to flow and three resistors (resistors are drawn as zig-zags). When components are wired one after another, as here, they are said to be in series. By Kirchhoff's Voltage Law, because the voltage rise is $$20$$ volts, the total voltage drop must also be $$20$$ volts. Since the resistance from start to finish is $$10$$ ohms (the resistance of the wires is negligible), we get that the current is $$(20/10)=2$$ amperes. Now, by Kirchhoff's Current Law, there are $$2$$ amperes through each resistor. (And therefore the voltage drops are: $$4$$ volts across the $$2$$ oh m resistor, $$10$$ volts across the $$5$$ ohm resistor, and $$6$$ volts across the $$3$$ ohm resistor.)

The prior network is so simple that we didn't use a linear system, but the next network is more complicated. In this one, the resistors are in parallel. This network is more like the car lighting diagram shown earlier. We begin by labeling the branches, shown below. Let the current through the left branch of the parallel portion be $$i_1$$ and that through the right branch be $$i_2$$, and also let the current through the battery be $$i_0$$. (We are following Kirchoff's Current Law; for instance, all points in the right branch have the same current, which we call $$i_2$$. Note that we don't need to know the actual direction of flow— if current flows in the direction opposite to our arrow then we will simply get a negative number in the solution.) The Current Law, applied to the point in the upper right where the flow $$i_0$$ meets $$i_1$$ and $$i_2$$, gives that $$i_0=i_1+i_2$$. Applied to the lower right it gives $$i_1+i_2=i_0$$. In the circuit that loops out of the top of the battery, down the left branch of the parallel portion, and back into the bottom of the battery, the voltage rise is $$20$$ while the voltage drop is $$i_1\cdot 12$$, so the Voltage Law gives that $$12i_1=20$$. Similarly, the circuit from the battery to the right branch and back to the battery gives that $$8i_2=20$$. And, in the circuit that simply loops around in the left and right branches of the parallel portion (arbitrarily taken clockwise), there is a voltage rise of $$0$$ and a voltage drop of $$8i_2-12i_1$$ so the Voltage Law gives that $$8i_2-12i_1=0$$.

\begin{array}{*{3}{rc}r} i_0&- &i_1   &-  &i_2   &=  &0 \\ -i_0&+ &i_1   &+  &i_2   &=  &0  \\ & &12i_1  &   &      &=  &20  \\ & &       &   &8i_2  &=  &20  \\ & &-12i_1 &+  &8i_2  &=  &0 \end{array} $$

The solution is $$i_0=25/6$$, $$i_1=5/3$$, and $$i_2=5/2$$, all in amperes. (Incidentally, this illustrates that redundant equations do indeed arise in practice.)

Kirchhoff's laws can be used to establish the electrical properties of networks of great complexity. The next diagram shows five resistors, wired in a series-parallel way. This network is a Wheatstone bridge (see Problem 4). To analyze it, we can place the arrows in this way. Kirchoff's Current Law, applied to the top node, the left node, the right node, and the bottom node gives these.

 * $$\begin{array}{rl}

i_0    &=  i_1+i_2  \\ i_1    &=  i_3+i_5  \\ i_2+i_5 &= i_4      \\ i_3+i_4 &= i_0 \end{array}$$

Kirchhoff's Voltage Law, applied to the inside loop (the $$i_0$$ to $$i_1$$ to $$i_3$$ to $$i_0$$ loop), the outside loop, and the upper loop not involving the battery, gives these.

 * $$\begin{array}{rl}

5i_1+10i_3 &= 10   \\ 2i_2+4i_4  &= 10   \\ 5i_1+50i_5-2i_2 &= 0 \end{array}$$

Those suffice to determine the solution $$i_0=7/3$$, $$i_1=2/3$$, $$i_2=5/3$$, $$i_3=2/3$$, $$i_4=5/3$$, and $$i_5=0$$.

Networks of other kinds, not just electrical ones, can also be analyzed in this way. For instance, networks of streets are given in the exercises.

Exercises
Many of the systems for these problems are mostly easily solved on a computer.

''There are networks other than electrical ones, and we can ask how well Kirchoff's laws apply to them. The remaining questions consider an extension to networks of streets.''

/Solutions/


text: Linear Algebra/Input-Output Analysis M File