Transcript 03.Preliminaries

PRELIMINARIES
CONTENTS
 Linear Algebra
 Convex Analysis
Reference: Chapter 2 in BJS book.
1
Vectors
Row or Column Vector:
An n vector is a row or column array of n numbers. Each n
vector can be represented by a point or by a line from the
origin to the point, with an arrowhead at the end point of the
line.
Zero Vector:
A vector whose every element is zero.
ith Unit Vector:
A vector whose every element is zero except the ith element
which is 1.
Sum Vector:
The vector with all elements equal to 1. Denoted by “1”.
2
Vector Operations
Addition of two vectors:
a1 = (a11, a12, a13, …. , a1n)
a2 = (a21, a22, a23, …. , a2n)
a1 + a2 = (a11 + a21, a12 + a22, a13 + a23, …. , a1n+ a2n)
Scalar multiplication:
a = (a1, a2, a3, …. , an)
ka = (ka1, ka2, ka3, …. , kan)
Inner product (scalar product):
a = (a1, a2, a3, …. , an)
b = (b1, b2, b3, …. , bn)
ab = a1b1 + a2b2 + a3b3 + … + anbn
3
Vector Operations (contd.)
Norm of a vector:
Various norms (measures of size) of a vector can be used.
lp norm of a vector a:
p
p
nj=1| a j |
Euclidean norm (l2 norm) :
2
nj=1a j
Euclidean space:
An n-dimensional Euclidean space, denoted by En, is the
collection of all vectors of dimension n
4
Linear and Affine Combinations
A vector b in En is said to be a linear combination of a1, a2, …,
ak in En, if
(i) b =  j=1λ ja j
k
(ii) 1, 2, … , k are real numbers.
A linear combination is said to be an affine combination if
kj=1λ j  1
5
Linear and Affine Subspaces
A linear subspace SL of En is a subset of En such that if a1 and
a2  SL, then every linear combination of a1 and a2 belongs to
SL.
An affine subspace SA of En is a subset of En such that if a1
and a2  SA, then every affine combination of a1 and a2 belongs
to SA.
6
Linear Independence
A collection of vectors a1, a2, … , ak of dimension n is called
linearly independent if
kj=1λ ja j = 0 implies that j = 0 for j = 1, 2, …, k
A collection of vectors a1, a2, … , ak of dimension n is called
linearly dependent if there exist j for j = 1, 2, …, k, not all zero
such that
kj=1λ ja j = 0
7
Spanning Set
Spanning Set: A collection of vectors a1, a2, … , ak in En is said
to span En if any vector in En can be represented as a linear
combination of a1, a2, … , ak.
In other words, given any vector b in En, we must be able to
find scalars 1, 2, … , k such that b = Sj=1,k jaj.
8
Basis
Basis: A collection of vectors forms a basis of En if the
following conditions hold:
(i)
(ii)
a1, a2, … , ak span En.
If any of the vectors is removed, the remaining collection
does not span En.
Question:
If we have a basis of En, what is the condition that will
guarantee that if a vector of the basis, say aj, is replaced by
another vector, say ap, then the new set of vectors still forms a
basis?
9
Matrices
A matrix is any rectangular array of numbers. The number in
the ith row and jth column of a matrix A is called the ijth element
of A and is denoted by aij.
A typical mxn matrix:
"mxn" is called the order of the matrix.
Equality of Matrices: Two matrices A = [aij] and B = [bij] are said
to be equal if and only if A and B are of the same order and aij =
bij for all i and all j.
10
Matrix Operations
Scalar Multiple of a Matrix:
 1 2
 3 6
A
; 3A  


 1 0 
 3 0
Addition of Two Matrices:
1 2 3 
 1 2 3
A
; B


0 1 1
 2 1 1
0 0 0 
A B  

2
0

2


11
Transpose of a Matrix
Transpose of a matrix A is denoted by AT.
 a11 a12
a
a
21
22

A
 ..
..

 am1 am 2
 a11 a21
a
a
12
22
T

A 
 ..
..

 a1n a2 n
12
.. a1n 

.. a2 n 
.. .. 

.. amn 
.. am1 
.. am 2 
.. .. 

.. amn 
Matrix Operations (contd.)
The matrix product C = A B of an mxr matrix and rxn matrix B
is the mxn matrix C defined as follows:
ijth element of C = scalar product of row i of A and column j of
B
13
Special Matrices
Zero Matrix:
An nx m matrix is called a zero matrix if each entry in the
matrix is zero.
Square Matrix :
A matrix for which m = n.
Identity Matrix In:
An nxn square matrix for which aij = 1 if i = j, and aij = 0 if i≠j.
Triangular Matrix:
A square nxn matrix is called an upper triangular matrix if all
the entries below the diagonal are zeros. Similarly, a square
matrix is called a lower triangular matrix if all elements above
the diagonal are zeros.
14
Systems of Linear Equations
A linear system of m equations in n variables is:
A solution to a system of m equations in n unknowns is a set
of all possible values for the unknowns x that satisfies each
of the system's m equations.
15
Matrix Representation of a System of Equations
The above system of equations can be represented as
Ax = b,
where
16
Solving Systems of Linear Equations
We will describe the Gauss-Jordan method for solving a
system of linear equations. Using this method, we show that
any system of linear equations must satisfy one of the
following three cases:
Case 1 : The system has no solution.
Case 2 : The system has a unique solution.
Case 3 : The system has an infinite number of solutions.
The Gauss-Jordan method proceeds by performing three types
of elementary row operations (ero).
17
Type 1 ero
This ero transforms a given matrix A into a new matrix A' by
multiplying a row of A by a nonzero scalar.
Example: A'=3A:
18
Type 2 ero
Multiply row i of A by a number c ≠ 0 and add to some row j ≠ i:
row j of A' = c(row i of A) + (row j of A)
Multiply row 2 of A by 4 and add to row 3.
19
Type 3 ero
Interchange any two rows of A. For example, interchanging
rows 1 and 3 of A, we obtain
20
Gauss – Jordan Method
This method solves a system of linear equations by utilizing
ero's in a systematic fashion. We illustrate the method using
the following linear system:
2x1
2x1
x1
+
-
2x2
x2
x2
+
+
+
x3
2x3
2x3
=
=
=
9
6
5
The augmented matrix representation of the above system:
21
Gauss – Jordan Method (contd.)
By performing a sequence of ero's we can transform the above
system to
This system has a unique solution x1 = 1, x2 = 2 and x3 = 3.
We transform the system column by column, starting at the
first column and going up to the last column.
22
Gauss – Jordan Method (contd.)
23
When Do We Need Type 3 ero?
When the diagonal element is zero.
24
System With No Solution
x1
2x1
+
+
2x2
4x2
=
=
3
4
The above system has no solution.
RESULT: If we apply the Gauss-Jordan method to a linear system and
obtain a row of the form [0 0 ..... 0 | c] where c ≠ 0, then the original
linear system has no solution.
25
System with Infinite Solutions
x1 + x2
=1
+ x2 + x 3 = 3
x1 + 2x2 + x3 = 4
x1
x2
- x3
+ x3
= -2
= 3
26
Inverse of a Matrix
For a given mxm matrix A, the mxm matrix B is the inverse
of A if
BA = AB = Im.
The inverse matrix, if it exists, is unique.
We denote the inverse of the matrix A by A-1.
If A has an inverse, A is called nonsingular; otherwise it is
called singular.
Given an mxm matrix A, it has an inverse if and only if the
rows of A are linearly independent or, equivalently, if the
columns of A are linearly independent.
27
Calculation of the Inverse (contd.)
The inverse matrix, if it exists, can be obtained through a
finite number of ero’s.
The elementary row operations that reduce A to the identity
matrix, also reduce (A, I) to (I, A-1)
28
Example 1 (A-1 Exists)
Consider the matrix A. Construct [A, I]
 2 1 1
A   1 2 1 


 1 1 2 
 2 1 1 1 0 0
 A, I    1 2 1 0 1 0 
 1 1 2 0 0 1 
29
Example 1 (A-1 Exists)
Divide the first row by 2. Add the new first row to the second
row and subtract it from the third row.
1 12

5
0
2

0  32

1
2
3
2
3
2
30
1
2
1
2
 12
0 0

1 0
0 1 
Example 1 (A-1 Exists) (contd.)
Multiply the second row by 2/5. Multiply the new second row
to the second row by –1/2 and add to the first row. Multiply
the new second row by 3/2 and add to the third row.
1 0

0 1
0 0

1
5
3
5
2
5
 15
1
5
12
5
 15
2
5
3
5
31
0

0
1 
Example 1 (A-1 Exists) (contd.)
Multiply the third row by 5/12. Multiply the new third row by
–3/5 and add to the second row. Multiply the new third row by
–1/5 and add to the first row.
1 0 0

0
1
0

0 0 1  121
5
12
3
12
32

3
12
3
12
3
12
 121 
3 
 12 
5 
12 
Example 1 (A-1 Exists)
Therefore, the inverse of A exists and is given by:
A 1
 5 3 1 
1 

3 3 3 

12 
5 
 1 3
33
Example 1 (A-1 Does Not Exists)
Consider the matrix A. Construct [A, I]
 1 1 2
A   2 1 1 


 1 2 3
1 1 2 1 0 0


A
,
I

2

1
1
0
1
0
  

 1 2 3 0 0 1 
34
Example 1 (A-1 Does Not Exists)
Multiply the first row by –2 and add to the second row.
Multiply the first row by –1 and add to the third row.
2
1 1
 0 3 3

1
 0 1
35
1 0 0

2 1 0

1 0 1 
Example 1 (A-1 Does Not Exists)
Multiply the second row by –1/3. Then multiply the new
second row by –1 and add to the first row. Multiply the new
second row by –1 and add to the third row.
1 0 1
0 1 1

 0 0 0
0

2 / 3 1 / 3 0

5 / 3 1 / 3 1 
1/ 3
1/ 3
There is no way that the left-hand side matrix can be
transformed into the identity matrix by elementary row
operations, hence the matrix A has no inverse.
36
Properties of the Inverse Matrix
1. If A is nonsingular, then At is also nonsingular and (At)-1 =
(A-1)t.
2. If A and B are both n x n nonsingular matrices, then AB is
nonsingular and (AB)-1 = B-1A-1.
3. A matrix A is nonsingular if and only if its determinant
(det(A)) is nonzero.
4. A triangular matrix (either lower or upper triangular) with
nonzero diagonal elements has an inverse. This can be
easily established by noting that such a matrix can be
reduced to the identity by a finite number of elementary
row operations. In particular, let D = diag {d1,…..,dn} be a
diagonal matrix with diagonal elements d1,….,dn and all
other elements being zero. If d1,….,dn are all nonzero,then
D-1 = diag {1/d1,…..,1/dn}.
37
Rank of a Matrix
Let A be an mxn matrix.
The row rank of the matrix is equal to the maximum number
of linearly independent rows of A.
The column rank of A is the maximum number of linear
independent columns of A.
The row rank of A is always equal to its column rank.
38
Rank of a Matrix (contd.)
How to determine the rank of a matrix?
39
Rank of a Matrix (contd.)
rank (A)  minimum (n,m)
If rank (A) = minimum (n,m), then A is said to be of full rank.
The rank of A is k if and only if A can be reduced by
performing ero’s to
 Ik
0

Q

0
40
Convex and Strict Convex Combinations
For any two points x1 and x2 in X, any point
x1 +(1- )x2 with 0    1,
is called a convex combination of x1 and x2.
A strict convex combination of x1 and x2 is any point
x1 +(1- )x2 with 0 <  < 1.
41
Convex Functions
A function f(x) is said to be a convex function if the
following inequality holds for any two vectors x1 and x2:
f(x1 + (1 - )x2)  f(x1)+ (1- )f(x2) for all 0    1
Loosely speaking, a function is a convex function if the line
joining any two points is an overestimate of the function.
Which of the following functions are convex functions?
x2
x2
x2
x1
x1
42
x1
Concave Functions
A function f(x) is said to be a concave function if the
following inequality holds for any two vectors x1 and x2:
f(x1 + (1 - )x2)  f(x1)+ (1- )f(x2) for all 0    1
Loosely speaking, a function is a concave function if the line
joining any two points is an underestimate of the function.
Which of the following functions are concave functions?
x2
x2
x2
x1
x1
43
x1
Convex Sets
 A set of points S is a convex set if the line segment
joining any pair of points in S is wholly contained in S.
 A set S is a convex set if every convex combination of
any two points in the set is also in the set. That is,
If x1  S and x2  S,
then x1 + (1-)x2  S for every 0    1
44
Extreme Points
A point x in a convex set X is called an extreme point of X if
and only if x cannot be represented as a strict convex
combination of two distinct points in X.
Give the extreme points of the following sets:
45