## Setting Up And Solving Linear Algebra Problems

### Topics:

[Back to main page] [Back to numerics page]

### Converting problems to systems and systems to variables

Knowing when a problem is expressible as a set of coupled, linear algebraic equations is key to using the mathematics of linear algebra to get a solution to your problem. To use the methods of linear algebra to solve your problem, you need to generate two key objects:

1. the coefficient matrix (A)
2. the left-hand side vector (b)

Once these are identified and created, you can then get a solution to your problem.

Procedure for setting up a matrix problem and getting it set up in MATLAB.

1. Make sure the problem is linear in the unknown variables (the xi's). Each unknown variable must appear alone and only to the first power. If this is not true, then your problem is not a linear problem and linear algebra cannot be used to directly solve your problem.

Example: The equations

x + 4y = 2z
x + 2xy - z2 = 14

do not form a linear set of equations due to the mixed term, 2xy and the squared z-term.

2. Arrange your equations so that the unknown variables (and the coefficients that multiply them) appear on the left-hand side of each equation. All constants should appear on the right-hand side of each equation.

To save time and reduce the chance for errors, pick an ordering for the unknowns and use that ordering in all equations. Also, if an unknown is missing from an equation, write that unknown into your equations by giving it a coefficient of 0 for the particular equation. Be sure to include zeros on the right-hand side if no constant is involved.

Example: If your equations look like

t + 2z - w = 5
w = t - 6z
5 - 4t = z

then pick an ordering for the unknowns (t, w and z, in this example) and re-write them as

t -  w + 2z = 5
t -  w - 6z = 0
4t - 0w +  z = 5

Lining up the variables in each equation is a Very Good Thing as it helps you visually check your work.

3. Extract the coefficient matrix by writing the values that multiply each of the unknowns in each equation in a tabular form, one row for each equation and one column for each variable. Be sure to keep the order of the variables consistent in each row.

Example: Using the final results from the last example, the rows of the coefficient matrix for this problem are

Eq. 1/Row 1:  1  -1   2
Eq. 2/Row 2:  1  -1  -6
Eq. 3/Row 3:  4   0   1

4. Extract the right-hand side vector by writing the values that appear on the right-hand side of each equation in a tabular form, one value per row.

Example: Using the example above,

Eq. 1/Row 1:  5
Eq. 2/Row 2:  0
Eq. 3/Row 3:  5

5. Create MATLAB variables for the coefficient matrix and the right-hand side vector by directly entering the tables you created in the last two steps. If you have only a few equations and unknowns (3 or 4, usually) and just want an answer, entering in variables at the command line will suffice (see creating arrays). If the problem is larger or if you intend on using the matrix for more work, consider writing a script or function Mfile to create the arrays you need.

Example: The example used so far is small enough to do at the command line.

A = [1  -1   2      % row #1 - starts the definition
1  -1  -6           % row #2
4   0   1]          % row 3 - ends the definition

b = [5  0  5]'      % the transpose is important!

• Make sure the coefficient matrix (A) matches the coefficients in your equations and that the number of rows in A and b are the same (use size or whos to check this).

• Make sure b is a column vector.

• Make sure the number of columns in A is the same as the number of unknowns.

These may sound trivial for the example just given but, for larger problems, taking time to ensure a correct set-up is critical for getting meaningful results (if you get results at all!).

If you have successfully translated your equations to a coefficient matrix/right-hand side vector pair, you are ready to find solutions for the unknown quanitities in your problem.

### Solving a set of linear equations in MATLAB

If you are ready to solve for the unknowns in a set of coupled, linear equations, then you should have two objects ready to go either as workspace variables or variables that are created when a script or function runs:
1. The coefficient matrix (A)

2. The right-hand side vector (b)
If you are missing either of these, take a moment to create them.

### WARNING

Just because you have sucessfully created a coefficient matrix and right-hand side vector that represents your linear system of equations, do not assume that you will be able to find a solution. Beyond the mundane problems of typographical errors is the issue of whether or not a set of linear equations actually has a solution. For example, your set of equations may contain an equation that is a (linear) combination of two (or more) other equations in the set. Such an equation is called a linearly dependent equation. Linearly dependent equations are redundant equations - they provide no new information about the connection of the variables in the problem. When present, linearly dependent equations will stop you from obtaining a solution. A discussion of these issues is given below.

If you have the coefficient matrix stored in an array called A and the right-hand side vector in an array called b, then the solution to your problem is simply

x = A\b

which you should read as "A under b" or "b divided by A from the left".

That's it, from the solution procedure point of view. A few more details about solving sets of equations are available in the linear algebra summary page.

### Dealing with problems

OK. So A\b did not "work". Either you didn't get a solution or the solution is "wrong" in some sense. What could be the problem? Lots of things, most of which are not related to MATLAB (directly). Each problem is unique, more or less, and the following items give some avenues that might help you find what is "wrong" with your problem.

• Is there a typo in the function, script or command that created either the coefficient matrix or the right-hand side vector?

• Are the arrays involved (A, b) in the right "shape"? Review the steps for creating these items, focussing particularly on Step 6 ( Check Your Work). If you are dealing with a square (N-by-N) system, your coefficient matrix should be N-by-N and the right-hand side vector should be N-by-1. Are you sure you have entered A and not its transpose?

• If you are dealing with a square (N-by-N) system, is your coefficient matrix "of full rank" (i.e., is it rank-deficient)? You can check the rank of your matrix via
rank(A)

If the rank is not N, then there are N-rank(A) linearly dependent equations in your set. The problem usually is that you do not know which ones are linearly dependent. If this is your stumbling block, the best solution is to carefully review the formulation of your problem and the way it lead to the system of linear equations you are using. The discussion of solvability may help here.

• Does your matrix behave as if it were rank-deficient? Since the computer does not have infinite numerical precision, a matrix can appear to be rank-deficient when it "shouldn't be". One indication of such a condition is called the condition number of your matrix, computed via
cond(A)

Qualitatively, the (magnitude of the) logarithm of the condition number is about how may digits of accuracy you lose in the result you compute. For MATLAB (which operates using "double precision"), you have at most 15 or 16 digits to work with and so condition numbers above 1e10 should be cause for serious concern about accuracy.

### When are solutions possible?

A fundamental concern of the topic of linear algebra is to detemine the structure of the solutions to sets of linear equations. There are many nuances associated with this issue and a good book on linear algebra is recommended if you need more answers than I present here. I find the 3rd edition of Noble and Daniels' "Applied Linear Algebra" (Prentice-Hall, 1988) to be an excellent reference if you are interested in getting a good hold on these ideas. The information that follows in this section is taken from Chapter 4 of this source.

Given a linear system represented by the coefficient matrix, A, and right-hand side vector, b, then three possibilities exist for the solution x of Ax = b:

1. No solution exists
2. Exactly one solution exists
3. Infinitely many solutions exists

A 2-by-2 system of equations simply illustrates these possibilites since you can visualize the nature of the solutions by drawing lines in 2D space.

• If no solution exists, the lines are parallel
• If one solution exists, the lines intersect
• If infinitely many solutions exist, the lines are coincident

The existence of solutions is usually described in terms of the rank of the coefficient matrix. The rank of a matrix tells you the number of independent rows (or columns) in the matrix and hence tell you the number of independent equations that are in your set. To get a unique solution, you need to have the rank of your coefficient matrix equal to the number of unknowns in your problem.

The following table summarizes the solvability of a system of equations in terms to the rank of various matrices:

#### Solvability criteria for a linear set of equations

The system Ax = b has ... when ...
no solution rank(A) < rank([A b])
one solution rank(A) = rank([A b]) = N
infinite number of solutions rank(A) = rank([A b]) < N

where A is M-by-N, x is N-by-1 and b is M-by-1. The notation [A b] means that b is appended to A as an additional column. The MATLAB function rank will determine the rank of a matrix. See the online help information for more on this function.

[Back to main page] [Back to numerics page]
Comments? Contact Jim Maneval at maneval@bucknell.edu