On Generating Large Dimensional,

Hand-Calculable Exercises and Applications

(in linear ALgebra).

Author: Jeff R. Knisley

Abstract: One of the challenges in Linear Algebra is in developing problems, projects, and exercises that are both larger dimensional and student-accessible.  Indeed, round-off error, computational complexity, difficulty factoring characteristic polynomials of degree 3 or higher, and similar aspects often mean that any problems or applications of rank 3 or higher are approached solely via technology.

However, that same technology can be used to create student-accessible problems and applications of ranks 4 or 5 or even higher, even allowing the creation -- if desired -- of a technology-free course featuring only hand-calculable problems. In this presentation, we present a freely downloadable Maple worksheet that produces these types of problems. Moreover, it can be used to create hand-calculable applications of arbitrarily large rank involving stochastic matrices, eigenvalues and eigenvectors, Leslie matrix models, the simplex method, and several others.

I.  An "application" that generates "large" examples and solves them step by step. 

   Example Title:     

Get started by creating a new example.  The "Create New Example" button brings up a dialogue in which one of several examples can be chosen.  The application then loads the step by step solution to this randomly generated example.  The arrow keys can be used to advance one, two, or all the slides at a time either forward or backward.  Examples are saved and during a given Maple session can be reloaded using the "Load Previous Example" button.

Examples can also be saved in the current directory as either LaTeX Articles or LaTeX Beamer files with the filename being the example name with .tex appended.

II.  Batch Save of multiple examples.

The currently defined example generators are SystemOfEquations, HomogeneousSystem,  RowReduction, PLUdecomposition, TestForIndependence, DeterminantWithRowOps, and InverseMatrix.   Each of these takes two arguments -- number of rows and number of columns (which shold be the same for the last two).

Each generator creates an example that students can do by hand -- i.e., everything simplifies without the fractions becoming unreasonable.  The output from a generator is a list of steps that is used to generate the presentations.  The commands SeqToArticle and SeqToBeamer then generate the presentations.  

For example, the sequence below generates a system of equations example and converts the resulting sequence into a LaTeX article.  

By default, the SeqToArticle and SeqToBeamer commands produce a string which can be saved as file.  If a filename is included as a second argument, then the string is saved as a file.  Consequently, it is possible to generate numerous examples for students using a simple Maple loop.  If pdfLaTeX is installed on your system, the files can also be compiled to pdf format on the fly.

For example, the execution group below produces 10 SystemOfEquations examples.  If you know that pdfLaTeX is installed on your system, then uncomment (i.e., delete the # sign from) the line that has the ssystem command.  

III.  Matrices and Solvers

The foundation for these "hand-solvable" problems is the collection of matrix generators

SquareMatrix(dimension)

RMatrix(rows, cols)

SystemMatrix(rows,cols)

LeslieMatrix(dimension)

StochasticMatrix (dimension)

PageRankMatrix(number_of_pages)

SimplexMatrix(number_of_variables, number_of_constraints)  

and the corresponding "solvers"

GESolver(RMatrix(rows,cols))
SystemSolver( RMatrix(rows,cols))
LUSolver( RMatrix( rows, cols )):

DetSolver( RMatrix( rows, cols )):

InverseSolver( SquareMatrix( rows, cols )):

IndependenceSolver( RMatrix( max(rows, cols), min(rows,cols) ) ):

The solvers produce the solutionLists from the given matrices.  There are many other options available as well.  

IV.  Linear Algebra Examples Currently only Partially Implemented

There are several applications that currently generate images and matrices, but for several reasons (e.g., my time) have not been implemented as example generators -- or equivalently, that are used only to generate LaTeX examples.  These include the five "generators"

GramSchmidtExample( dimension, NumberOfVectors)
LeslieMatrixExample(number_of_classes)
PageRankExample(number_of_pages)

SimplexMethodExample (number_of_variables, number_of_constraints)

Each of these currently generates at random a problem that can be solved by hand.  In each case, the data returned can be transformed into a solution similar to those implemented already; or equivalently, they can be used to generate unique problems for each student in a course.  

We'll finish up by discussing each of these individually.

To begin with, the GramSchmidtExample generator simply produces a set of vectors that is highly amenable to the GramSchmidt process.  The set may be linearly dependent, thus resulting in a answer with fewer vectors than the question.  This is illustrated below:

The Leslie Matrix example randomly generates a Leslie age-based population model.  The command LeslieMatrixExample generates a Leslie Matrix and the corresponding Leslie Model diagram.

The result is a model in which only those in the final age group reproduce.  Mathematically, this represents a model in which eigenvalues and eigenvectors are amenable to hand calculation, as is illustrated by the characteristic polynomial, dominant eigenvalue, and eigenvector for the dominant eigenvalue shown below:   

There is also a slightly more complicated Leslie Model.   To access it, simply put true as the last argument (i.e., it is true that you desire a more involved model).  Again,  it is hand-calculable with respect to the dominant eigenvalue and associated eigenvector, and it represents a model in which the last two ages classes reproduce.

The PageRankExample command generates two matrices and the corresponding figure.  The first matrix is the Markov transition matrix for an "internet" that is not regular (and hence not amenable to the full Perron-Frobeinius theory).  The first figure corresponds to this matrix.  

The second matrix implements the "Random Surfer" approach to create a completely connected network with a regular transition matrix.   This is illustrated below:

NOTE: Both the Leslie Model and PageRank examples make use of the NetworkFigure command, which is defined below.  This essentially redraws the graph of a network labeled with rational edge weights.

Finally, the SimplexMethodExample generates a simple maximization linear programming problem.  The output from SimplexMethodExample is the matrix of the problem including slack variables, the original problem, and the problem with the incorporation of slack variables.  To illustrate, we will use the two panels below and the Seq2MML command which combines several expressions into a single "presentation panel".   

The matrix Tableau of the linear programming problem has the objective in the last row and the z-variable coefficients in the next-to-last column.  This allows the use of natural row, column numbering in determining pivots.

Moreover, there is also a command SPivot which pivots and rescales the pivot row.  This allows the study of the simplex criteria for moving columns in and out of the basis as opposed to focusing on the row operations themselves.  A couple of examples of SPivot are shown below:

V.  Future Directions

There is much still to implement and many more partial efforts that could be finalized and incorporated.  In all likelihood, however, I will not do so until I teach Linear Algebra again and desire to add more such problem generators and revise some of the old ones.

Network diagram generator:

Legal Notice: © Maplesoft, a division of Waterloo Maple Inc. 2009. Maplesoft and Maple are trademarks of Waterloo Maple Inc. Neither Maplesoft nor the authors are responsible for any errors contained within and are not liable for any damages resulting from the use of this material.  This application is intended for non-commercial, non-profit use only. Contact the authors for permission if you wish to use this application in for-profit activities.