Transcript Basics of Matrix Algebra

Basics of Matrix Algebra
The Roots are in the tricks and tribulations of solving linear equations
Nethra Sambamoorthi, PhD
Ok, why do we need matrix algebra?
• Ok, real life problems(opportunities) are always mixed with more
than one or two variable problems – Opportunities are multivariate in
nature.
• With out the structural simplification of representation, solvability,
and systematic evaluation of solutions are not possible with out the
multivariate structures extracted in the form of matrices, which on
closer looks seems to have its own set of nice properties giving raise
to a form of algebra which simplifies the our understanding and
extension of the science of matrices.
The word “Algebra” means a system of working with letters and other general symbols to represent numbers and
quantities in formulae and equations
The story of lost receipts from a store… Solving
Equations to figure out unit prices of mango and
banana
x=unit price of a mango
y=unit price of a banana
2x+3y=9
5x+1y=16
The price and total receipts that Ren brought from the
store is lost and their Mom does not know the price of
a mango and banana. Ren, being mischievous tells Mom
that, Oh…, the price of a mango and banana can be
figured out with the above equations.
Jen, younger sister of Ren, solves these equations and
figures out the price of a mango and a price of a
banana, so that her mom can give right money to Ren to
buy 25 mangoes and 50 bananas. What is the amount
that Ren’s mom has to give Ren?
Solve this system of two equations in two unknowns
and figure out a solution
This will not work, if there are many many(say
20) items in the billing sheets across multiple
days, and items are missing on different days,
even if the price is same across days, because
of the tediousness and accuracy
maintenance. The question is, are there ways
to develop systematic steps of solving such
equations simplifying the method,
irrespective of number of equations, and
number of unknowns
There is a way.
For learning purposes, we will define simpler
problems and solve them
Rewriting equations in Matrix form
This representation of
rectangular system of
number is called a matrix
2 3
5 1
𝑥
𝑦
=
9
16
vector
vector
If I follow a consistent way of combining the variables x and y along with the coefficients
captured in rectangular form on its left so that it gets back my equation before, we are
good.
That will happen if I define systematically as multiply the first column (definition) first
row(definition) element of the first structure, with first element of the (x,y) vector
(definition), sum it with the second column first row (definition) with corresponding first
element on the right side (x,y) vector and equate it as 9.Similarly you can interpret how to
get 16.
We will write this as U2x2p2x1=t2x1 for two days of receipt for two items buying. A is number
of units matrix, p is price vector, and t is for total receipts vector.
Matrices, vectors, scalars…
• It turns out that by just studying the properties of the numerical structures such as matrices,
vectors, and scalars, we can create a systematic way of solving equations however
• big they are, and however
• Inconvenient those numbers are in terms of number of decimals they may carry…
• This is mathematically written as (Units matrix) (price vector) = (total price vector)
• Up= t
• If there is only one variable, say mango alone, then p=t/U (agree…?) or U-1 x t (agree…?). This is
easy to understand, interpret, and apply
• But we have a structure of rectangular collection of numbers and there are multiple units of
multiple items; so what does it mean to say U-1? How do I calculate it? What are the properties
of such a square or possibly rectangular collection of numbers? The subject of studying the
properties and algorithms of such rectangular collection of numbers is called the study of matrix
algebra. We will only go through some important collection of matrices that will help solve our
problems and as we go deeper into many of the analytics solutions we will bring more matrix
algebra into our discussions.
• U x U-1 = 1 ; U-1 x U = I; this defines UNIT matrix
• U1U2p=t ; then the order of usage of inverses are reversed. P=U-12U-11 . This defines the order of
inversion
An alternative way of writing the equations
is…
We will call a single number or its “variable representation”, a scalar. So there are 4 scalars in the 2
by 2 matrix that is used in capturing the quantities of mango and banana.
𝑥
𝑦 2 5 = 9 16
3 1
This is same as saying, I am transposing everything in the equation. (The representation is
consistent, as long as the “operation” of “transpose” is happening on both sides of the equation.
Otherwise, the equivalence in information is not carried out consistently correctly.
We will represent the transpose in symbol for as follows.
pTUT=tT
If the representation is in this form, here, though, I have to find a matrix that when multiplied on
the right side of the equation, say, matrix (UT)-1, then we will get the price vector.
So, as long as we are consistently working with the structures the previous one or the current one,
namely, pT UT x (UT)-1 =tT(UT)-1, we are good. We will get the right answer always.
The Key Question then is …
• What kind of matrix I need to find that, when I pre-multiply
𝟐 𝟑 𝑥
9
=
𝟓 𝟏 𝑦
16
on the left, and on the right side of the equation will yield the
following?
𝑐11
𝑐21
𝑐12 𝟐
𝑐22 𝟓
1 0
0 1
𝟑 𝑥
𝟏 𝑦
𝑥
𝑦
=
=
𝑐11
𝑐21
𝑐12 9
𝑐22 16
9𝑐11 + 16𝑐12
9𝑐21 + 16𝑐22
Verifying using Excel that the answers are the same…
Units matrix (U)
2
5
Inverse of U
3
1
Cost vector
-0.0769 0.23076923
0.38462 -0.1538462
9
16
Price Vector
3
1
T
Units matrix transposed(U )
2
3
5
1
T
Inverse of U
-0.0769 0.38461538
0.23077 -0.1538462
T
Cost vector transposed (C )
9
Price vector transposed(P T)
3
1
16
It comes with
formula such
as
MINVERSE
MMULT
TRANSPOSE
Properties of Row Echelon Transformations
• EE-1=E-1E
• (E-1)T=(ET)-1
• (E1E2)T=(E1)T(E2)T
Mathematically we want to find U-1 for a square
matrix U, which is called the inverse matrix of U.
• In the numerical example I showed earlier, we are clear that
• U-1xU; does this mean UxU-1 = I (identity matrix) ? The numerical calculations
verifies that, but that will be used as a property for the definition of inverse of
a matrix; what is implied by this property is that it does not matter, for the
applications of row echelon transformation, whether we use the augmented
Identity matrix on the right of U or on the left of U when we start constructing
for inverse
• (UT)-1UT = (U x U-1)T : We want this to happen; so we define the property
(AB)T=BTAT ; This simply means the order of row echelon transformations can
be reversed and still we will get the same inverse
• (Ut)-1 =(U-1)t : We want this to happen
So, How to Compute Such an Inverse matrix…? (Bring
about Identity matrix times the variable vector in the
left side of the equation?)
• Let us get back to the equations. The way we solve the equation will
become, what is called “sweeping method”, a method where we
sweep all the coefficients of “diagonal type variables” to “1” and
other coefficients to zero.
See specific three examples of what is called row echelon sweeping method to solve the problem in Khan academy;
Think about why Sal (Khanacadamy visionary) provides these three different examples.
https://www.khanacademy.org/math/precalculus/precalc-matrices/reduced_row_echelon/v/matrices-reduced-rowechelon-form-1
https://www.khanacademy.org/math/precalculus/precalc-matrices/reduced_row_echelon/v/matrices-reduced-rowechelon-form-2
https://www.khanacademy.org/math/precalculus/precalc-matrices/reduced_row_echelon/v/matrices-reduced-rowechelon-form-3
Big question: Can you guess how to get inverses using the same method but doing something in the place of cost
vector that is added at the end in these examples ….!!! Remember inverses are for the square matrix.
Ok,…, here is the way
Coeff. Matrix
Rewrite
cost
Indentity Matrix
2
3
5
1
1
0
0
1
9
16
Somehow (using linear transformations - multily by a constant, multiply another row and add/subtract with a given
row), make the b33, c33, b44, c44 as an identity matrix)
Step1
1
5
1.5000
1
0.5000
0
0
1
4.5000
16.0000
Step2
1 1.5000
0 (6.5000)
0.5000
(2.5000)
0
1
4.5000
(6.5000)
Step3
Step4
1
0
1
0
1.5000
1
0
1
1
0
0.3846
(0.1538)
Inverse of coeff.matrix
4.5000
1.0000
divide this row by 2 to get 1 in B71
Make B11,2 into 0 by multiplying above row by -5 and
adding here
Divide this row by the output of C11,2 from prev.calc
Price
(0.0769)
0.2308
3.0000
0.3846
(0.1538)
1
Make C16,2 to become 0
Once you get these foundation ideas well
ingrained…
• It is surprisingly simple to understand
• why the linear programming simplex solution approach works (remember it is always
important to know both how as well as why)
• What is meant by eigen vectors and eigen values, why do we need them?
• What is meant by decomposition of a square matrix as well as any general matrix
and how they are related to eigen vectors and eigen values? Are there eigen vectors
for a non-square matrices? How do we compute them?
• What is meant by singular value decomposition? Why do they matter?
• What is meant by g-inverse (generalized inverse of a matrix) and why it is needed?
• And, of course, more importantly how to solve least squares problem, which is the
reason why we started on this path.
All good stuff; suddenly you feel that you know how to easily work with this
strange looking items called matrices, wherever they penetrate…, and they
penetrate all of applied mathematics areas.
Eigen Vector, why it matters, and how to
find…?
• What if in the mango/banana receipt example, people eat only
proportionately. Then every week, they may decide to increase or
decrease all the items in the same proportion; that is every vector is a
proportion of one vector!
• Then there is only one vector that is needed to construct the whole
“number of units matrix”. There is only dimension to explain the whole
matrix!
• That is we are saying Ax=lIx that (A-lI)x=0, has one l solution; Instead of
only one vector that is needed, there are only two different vectors needed
however many number of receipts are there.
• Then what we are saying is that Ax=l1Ix1 and Ax=l2Ix2, for any possible
collection of receipts where mango and banana data are available. This is in
essence a data reduction idea!
Instead of two items, what happens we have
20 items…
• So instead of the following,
For two days and two items
you may end up having ,
𝟐
𝟓
𝟑
𝟏
𝑥
𝑦
9
16
for thirty days and twenty items
• A30x20x20x1=y20x1and lets say these are just samples that are representative of “all” the
receipts, except for systematic small sampling errors – white noise, the family will ever
have.
• So, what this means is that there seems to be a pattern in the receipts that when you
bring any day a receipt, then just using the limited (say, 2 or three) eigen vectors, I can
write the receipts as a linear function of those two key or kernel or eigen vectors.
Geometry of Matrix Transformations…
What is the importance of Eigen Values and
Eigen Vectors…?
• http://math.stackexchange.com/questions/23312/what-is-theimportance-of-eigenvalues-eigenvectors (descriptive answers)
• Why finding principal Eigen axes and Eigen vectors will help you in
utilizing the maximum information in a graphical illustration
A note on humble beginning of matrices:
Though solving systems of equations are the beginning, now it is
applicable in all kinds of sophisticated and huge problems of solving
complex non-linear, less than full rank systems of equations, including
linear and non-linear optimization problems, sparse data analysis, least
squares, data and image compression problems, computer vision
analysis, dimensionality reduction, dynamical systems, and so on.
Factor Analysis – An Introduction
Factor Analysis – A Model Representation –
Part 1
Factor Analysis – A Model Representation –
Part2
Factor Analysis – A Model Representation –
Part3
Factor Analysis – A Model Representation –
Part4
Linear Algebra 18a: Introduction to the Eigenvalue
Decomposition – Making Sense of Big data, Super
Big Data ….
A Worked Out Example of Eigen Values and
Eigen Vectors
An Important Implication of Eigen Values and
Eigen Vectors…
Eigen Values and Eigen Vectors as Generators
of Functions of a Matrix