Applications: Projects requiring solutions of systems

Solving systems of equations

Nodal analysis of circuits - Uses systems of equations to find the current through each loop of a circuit including batteries and resisters.  Nodal analysis creates linear equations using Kirchhoff's Laws of junctions and paths.  This is a popular project for students who have studied some physics.  One value of this project is the ability to create overdetermined, consistent systems of equations, which helps students understand rows of zeros in the RREF form of augmented matrices.  This article on Nodal Analysis of Electric Circuits has a clear explanation.

Loop analysis of circuits - Uses systems of equations to find the current through each loop of a circuit including batteries and resisters.  Loop analysis creates linear equations using Kirchhoff's Laws of loops.  Again, a popular project for students who have studied some physics and also has the opportunity for overdetermined, consistent systems.  Equivalent in results to nodal analysis, this could be combined or assigned separately.  This article on Loop Analysis of Electric Circuits has a clear explanation.

Curve fitting - Using systems of equations a student finds the coefficients of a polynomial of degree n - 1 to fit n points.  I don't think of this as a juicy application that gives the student an appreciation for how linear algebra is used in the world.  Fitting an n-degree polynomial to m points using least squares or other methods is more likely to happen.

Euler Characteristic and Planar Graphs

To the right we see a planar graph. It divides the plane into 5 regions which I have labeled A, B, C, D and E. We call region D a triangle because it has three sides. Regions B, C and D are quadrilaterals since they have 4 sides. Even though A is an infinite region in the plane, it has 3 sides and is called a triangle. The question we address here is whether we can draw planar graphs with all possible combinations of triangles, squares, pentagons, etc., or not. Also, can we determine which combinations are possible?

We will use the Euler Characteristic for the sphere to solve this problem. I know it looks like the figure above is drawn on the plane, but you can also think of it as drawn on a relatively flat part of a sphere. In this way, region A is not infinite, but we will still call the regions triangles, quadrilaterals, pentagons, etc., even though they now have a curve to them. The Euler Characteristic is V – E + R, where V = number of vertices, E = number of edges (not the region E above) and R = number of regions. The Euler Characteristic depends only on the surface on which the planar graph is drawn, and not the shape of the graph. For the sphere,

V – E + R = 2,

always. In the example at the above, V – E + R = 6 – 9 + 5 = 2.

Let’s do a little counting. In the figure above, E = 9 is the number of edges. However, if we count the sides of the polygons we get 2 triangles x 3 sides each + 3 quadrilaterals x 4 sides each = 18 sides. This is twice as many as the edges, because polygon each side is counted twice for each edge, once for the polygon on one side of the edge and once for the polygon on the other side of the edge. For instance, in the edge count, E, the edge xy is counted for the triangle D and the quadrilateral C.

What about the vertices? In the figure above V = 6is the number of vertices. If we count the vertices of the polygons we get 2 triangles x 3 vertices each + 3 quadrilaterals x 4 vertices each = 18. In this case, we get three times as many polygon vertices as graph vertices because there are three polygons meeting at each vertex. For example, polygons A, B and C meet at vertex t.

These counting techniques and the Euler Characteristic will give us a system of equations for finding whether graphs with certain combinations of polygons are possible. 

Example 1: Can we draw a planar graph with only triangles so that exactly three triangles meet at each vertex? If so, how many triangles will there be? We can answer this question with a system of linear equations. The first equation is the Euler Characteristic for the sphere:

V – E + R = 2.

Each region is 3 sided, but if we count 3R sides that will be double the edges since each side is counted twice:

3R = 2E.

Each region has 3 vertices, but if we count 3R vertices that will be triple the total vertices since three triangles meet at each vertex:

3R = 3V.

Solve this square system of 3 equations in 3 unknowns using your favorite method, and we find there is only one way to do this:

V = 4, E = 6 and R = 4.

The only solution is to have 4 triangles, 4 vertices and 6 edges as shown on the right, remembering that the outside region is a triangle.  So, we could never draw a graph that had 5 triangles such that 3 triangles meet at each vertex.  Give it a try to see why it can't be done.

Questions: Can we draw a planar graph of triangles where 4 triangles meet at each vertex? 5 triangles meet at each vertex? 6 triangles meet at each vertex? How would we change the system above to answer these questions.  If the graph exists, try to draw it. 

Example 2: What if there are two different types of polygons? Consider a graph of triangles and quadrilaterals, assuming that three polygons meet at each vertex. We will introduce two new variables: T and Q, the counts of the triangles and quadrilaterals, respectively. Now, the total number of regions is the sum of the two types of polygons,

T + Q = R.

Count the edges, 3 for each triangle and 4 for each quadrilateral, and as in Example 1, this counts each edge twice:

3T + 4Q = 2E.

Count the vertices, 3 for each triangle and 4 for each quadrilateral, and as in Example 1, this counts each vertex thrice, because 3 polygons meet at each vertex:

3T + 4Q = 3V.

Finally, we need the Euler Characteristic:

V – E + R = 2.

This time we’ll use a matrix and row reduction to get the solution. The system is underdetermined, so we expect to get infinitely many solutions.

Sure enough, we have a free variable and we can write the general solution as

T = 12 – 2R,
Q = –12 + 3R,
V = –4 + 2R and
E = –6 + 3R.

But in this application, the values of T, Q, V and E have physical meaning and must be positive. If V or E is zero, then the graph would be empty. We could assume that T or Q is zero, but we are interested in graphs with both triangles and squares. Now we can solve the inequalities below to see if there is a viable solution, and how many there are.

T = 12 – 2R > 0      =>      R < 6
Q = –12 + 3R > 0      =>      R > 2
V = –4 + 2R > 0      =>      R > 2
E = –6 + 3R > 0      =>      R > 4

Okay, R is an integer and strictly between 4 < R < 6, so R = 5 is the only realistic solution to this underdetermined system. Now,

R = 5, T = 2, Q = 3, V = 6 and E = 9.

Draw this graph (don’t forget that the outside region is one of the 5 regions and must be either a quadrilateral or a triangle). The graph is at the bottom of this blog, but don’t peak before you give it a try.

Questions:

1. Can you draw a planar graph with pentagons and hexagons such that three polygons meet at each vertex? If so, how many of each polygon are there? Can you draw them?

2. Can you draw a planar graph with triangles and quadrilaterals such that four polygons meet at each vertex? I have written the equations and solved the system for this case, and this may have infinitely many solutions, but I haven’t had the time to draw more than two of the solutions and would like to see an algorithm for drawing all of them.

3. Other surfaces, such as a torus (donut) have different Euler Characteristics. How does one draw a graph on a torus? What are the solutions to the questions above if the graphs live on a torus?  Wolfram MathWorld has a list of the Euler Characteristics for surfaces, but WikiPedia has nice images of those surfaces if you scroll to the bottom of the article.

To limit this blog to a few pages, a lot is left unsaid. But again, these posts aren’t meant to give an in-depth discussion of the topic, but just an introduction.  Go exploring for more about this topic.

Reference: Alain M. Robert, An Approach of Linear Algebra through Examples and Applications

Solving Balance Puzzles with Matrices

I grew up on puzzles and games. A typical Christmas or birthday present was a puzzle book, and our family spent a lot of quality time together when the Games magazine came in the mail. Being the math nerd that I am, I would sometimes use trial and error for the puzzles, but anything I could convert into equations to solve was a bonus. So, in a way, I was introduced to linear algebra long before I took the class in undergraduate school.

These puzzles are from Games magazine, and I hope they forgive me for forgetting the specific issue for a complete citation. They provide a nice visual from which systems of equations can be developed. These systems tend to be underdetermined; however, there are added restrictions on the solutions--they must be integers within a certain range. Thus, these underdetermined systems have a finite number of solutions instead of infinite, specifically because equations are over a range of integers, not over the reals.

Think of these puzzles like building a mobile, where the objects on each side must balance so that the horizontal bars stay horizontal under the following rules.

• each shape represents a unique positive weight
• each weight is an integer N such that 0 < N < 100
• the right and left sides of each horizontal beam must balance
• a piece hanging directly below the fulcrum does not affect the balance between the left and right arms
• the size of the pieces has no relation to weight
• these are exercises in balancing number values and do not take into account the distance from the fulcrum

Example 1: For the mobile at the top of the page, the total weight is 36. I have labelled each weight with a variable name, A, B and C. The total weight is 36:

A + 2B + 2C = 36.

The left arm must balance the right arm:

A + 2B = 2C or A + 2B - 2C = 0.

We create an augmented matrix for this system and row reduce:

While using a matrix was not necessary for this simple problem, it will be useful for the larger systems below. So, C = 9, B is a free variable, and the general solution is

(A, B, C) = (18 - 2B, B, 9)

with some restrictions on B. Since 0 < A < 100,

0 < 18 - 2B < 100,

-18 < -2B < 82, and

9 > B > -41.

Since B > 0, we find 0 < B < 9, and thus, there are 8 possible answers, one each for B = 1, 2, 3, 4, 5, 6, 7 and 8.

Questions: First, solve the puzzles below, then consider these questions.

1. What would it take to create one of these puzzles? Can you create a puzzle that has a unique solution?
2. How would it change if we did consider distance from the fulcrum? Would it still be a linear system? If so, create a simple puzzle where distance is considered.
3. What determines how many equations are required? For instance, in Puzzle 1 below how many equations are described?  Don't forget that each horizontal bar needs to balance, not just the top one.

Puzzle 1. The total weight is 80. Only one shape weighs more than 9 and the cube is 1 unit heavier than the octahedron.

Puzzle 2. The total weight is 54. The three arms are equal in weight.

Puzzle 3. The total weight is 180. The three arms are equal in weight.

---------------------------------------------

A later post - December 31, 2011

I found a link with more balance puzzles.  These are different looking, but the idea is the same.  In this case you need to take the distance each weight is offset from the balance point into account.  For example, a weight of 2 units that is 1 unit from the fulcrum will balance a weight of 1 unit that is 2 units from the fulcrum.  Can you use linear algebra to solve these puzzles?  If so, how?

Here is another page of balance puzzles.http://battleships.free.fr/balance_i.pdf

Solving Number Puzzles with Matrices

The Discovery Education Classroom Resources has some great classroom tools. One of my favorites is Puzzle Master. It allows you to create custom puzzles like word searches or cryptograms. I used the Number Blocks puzzle creator for a linear algebra project on overdetermined and underdetermined systems of equations.

An example of a number block puzzle created using Puzzle Master is given above. The numbers to the right an bottom are the sums of various rows, colums and diagonals of the 3-by-3 grid of numbers. The main diagonal sums to 14; the off diagonal sums to 17. The sum of each row is to the right, and the sum of the columns is at the bottom. In this example, there are 6 unknowns and 8 equations, and so this is an overdetermined but consistent system. Puzzle Master will not create a puzzle that does not have a solution.

Questions:  We can create a system of equations for this number puzzle as shown above. There are a lot of questions that can be asked about these number puzzles and the systems that can solve them.

• Given an n-by-n grid of numbers, how many equations are needed to solve the puzzle?
• What determines how many unknows there are?
• Given an n-by-n grid of numbers, how many unknowns must there be for the system to be overdetermined? Underdetermined? Square?
• Are there equations in the system below that can be removed so that the system is not overdetermined but has an equivalent solution? If so, how many and which equations can be removed.
• If a number puzzle is underdetermined, how can a solution be found?
• Is it possible for a number puzzle to have exactly two different solutions? Exactly five different solutions? Explain.
• Is it possible for a number puzzle to have infinitely many solutions? Describe a puzzle for which this would be true, and explain how to describe the infinitely many solutions.
• Puzzle Master won't create a puzzle with no solution, but can you create a puzzle that has no solution and is overdetermined? Underdetermined? Square?
• Create a puzzle using Puzzle Master that would have infinitely many solutions. Can you make a conjecture on how Puzzle Master chose the solution that it gives?