- Mathematics for Algorithmic
- Sets
- Vectors and Matrices
- Linear Inequalities and Linear Equations
Sets
S. On the the hand, if x is not a member of S, we write z 
S. A set cannot contain the same object more than once, and its elements are not ordered.For example, consider the set S= {7, 21, 57}. Then 7
{7, 21, 57} and 8 {7, 21, 57} or equivalently, 7 S and 8 S.We can also describe a set containing elements according to some rule. We write
{n : rule about n}
Thus, {n : n = m2 for some m
N } means that a set of perfect squares.Set Cardinality
The number of elements in a set is called cardinality or size of the set, denoted |S| or sometimes n(S). The two sets have same cardinality if their elements can be put into aone-to-one correspondence. It is easy to see that the cardinality of an empty set is zero i.e., |
| .Mustiest
If we do want to take the number of occurrences of members into account, we call the group a multiset.
For example, {7} and {7, 7} are identical as set but {7} and {7, 7} are different as multiset.
Infinite Set
A set contains infinite elements. For example, set of negative integers, set of integers, etc.
Empty Set
Set contain no member, denoted as
or {}.Subset
For two sets A and B, we say that A is a subset of B, written A
B, if every member of A also is a member of B.Formally, A
B ifx A implies x B
A implies x Bwritten
x A => x B.
A => x B.Proper Subset
Set A is a proper subset of B, written A
B, if A is a subset of B and not equal to B. That is, A set A is proper subset of B if A B but A 
B.Equal Sets
The sets A and B are equal, written A = B, if each is a subset of the other. Rephrased definition, let A and B be sets. A = B if A
B and B A.Power Set
Let A be the set. The power of A, written P(A) or 2A, is the set of all subsets of A. That is, P(A) = {B : B
A}.For example, consider A={0, 1}. The power set of A is {{}, {0}, {1}, {0, 1}}. And the power set of A is the set of all pairs (2-tuples) whose elements are 0 and 1 is {(0, 0), (0, 1), (1, 0), (1, 1)}.
Disjoint Sets
Let A and B be sets. A and B are disjoint if A
B = .Union of Sets
The union of A and B, written A
B, is the set we get by combining all elements in A and B into a single set. That is,AB = { x : x A or x B}.
B = { x : x A or x B}.For two finite sets A and B, we have identity
|AB| = |A| + |B| - |A
B|
B| = |A| + |B| - |AB|We can conclude
|AB| 
|A| + |B|
B| |A| + |B|That is,
if |AB| = 0 then |AB| = |A| + |B| and if A B then |A| |B|
B| = 0 then |AB| = |A| + |B| and if A B then |A| |B|Intersection Sets
The intersection of set set A and B, written A
B, is the set of elements that are both in A and in B. That is,AB = { x : x A and x B}.
B = { x : x A and x B}.Partition of Set
A collection of S = {Si} of nonempty sets form a partition of a set if
i. The set are pair-wise disjoint, that is, Si, Sj and i j imply Si Sj = .
and i j imply Si Sj = .ii. Their union is S, that is, S = Si
SiIn other words, S form a partition of S if each element of S appears in exactly on Si.
Difference of Sets
Let A and B be sets. The difference of A and B is
A - B = {x : x A and x B}.
A and x B}.For example, let A = {1, 2, 3} and B = {2, 4, 6, 8}. The set difference A - B = {1, 3} while B-A = {4, 6, 8}.
Complement of a Set
All set under consideration are subset of some large set U called universal set. Given a universal set U, the complement of A, written A', is the set of all elements under consideration that are not in A.
Formally, let A be a subset of universal set U. The complement of A in U is
A' = A - U
OR
A' = {x : x U and x A}.
U and x A}.For any set A
U, we have following lawsi. A'' = A
ii. A A' = .
iii. A A' = U
ii. A
A' = .iii. A
A' = USymmetric difference
Let A and B be sets. The symmetric difference of A and B is
A
B = { x : x A or x B but not both}
B = { x : x A or x B but not both}Therefore,
A B = (AB) - (AB)
B = (AB) - (AB) As an example, consider the following two sets A = {1, 2, 3} and B = {2, 4, 6, 8}. The symmetric difference, A
B = {1, 3, 4, 6, 8}.Sequences
A sequence of objects is a list of objects in some order. For example, the sequence 7, 21, 57 would be written as (7, 21, 57). In a set the order does not matter but in a sequence it does.
Hence, (7, 21, 57)
{57, 7, 21} But (7, 21, 57) = {57, 7, 21}.Repetition is not permitted in a set but repetition is permitted in a sequence. So, (7, 7, 21, 57) is different from {7, 21, 57}.
Tuples
Finite sequence often are called tuples. For example,
(7, 21) 2-tuple or pair
(7, 21, 57) 3-tuple
(7, 21, ..., k ) k-tuple
(7, 21, 57) 3-tuple
(7, 21, ..., k ) k-tuple
An ordered pair of two elements a and b is denoted (a, b) and can be defined as (a, b) = (a, {a, b}).
Cartesian Product or Cross Product
If A and B are two sets, the cross product of A and B, written A×B, is the set of all pairs wherein the first element is a member of the set A and the second element is a member of the set B. Formally,
A×B = {(a, b) : a A, b B}.
A, b B}.For example, let A = {1, 2} and B = {x, y, z}. Then A×B = {(1, x), (1, y), (1, z), (2, x), (2, y), (2, z)}.
When A and B are finite sets, the cardinality of their product is
|A×B| = |A| . |B|
n-tuples
The cartesian product of n sets A1, A2, ..., An is the set of n-tuples
A1 × A2 × ... × An = {(a1, ..., an) : ai Ai, i = 1, 2, ..., n}
Ai, i = 1, 2, ..., n} whose cardinality is
| A1 × A2 × ... × An| = |A1| . |A2| ... |An|
If all sets are finite. We denote an n-fold cartesian product over a single set A by the set
An = A × A × ... × A
whose cardinality is
|An | = | A|n if A is finite.
Vectors and Matrices
A vector, u, means a list (or n-tuple) of numbers:
u = (u1, u2, . . . , un)
where ui are called the components of u. If all the ui are zero i.e., ui = 0, then u is called the zero vector.
Given vectors u and v are equal i.e., u = v, if they have the same number of components and if corresponding components are equal.
Addition of Two Vectors
If two vectors, u and v, have the number of components, their sum, u + v, is the vector obtained by adding corresponding components from u and v. u + v = (u1, u2, . . . , un) + (v1, v2, . . . , vn)
= (u1 + v1 + u2 + v2, . . . , un + vn)
Multiplication of a vector by a Scalar
The product of a scalar k and a vector u i.e., ku, is the vector obtained by multiplying each component of u by k: ku = k(u1, u2, . . . , un)
= ku1, ku2, . . . , kun
Here, we define -u = (-1)u and u-v = u +(-v)
It is not difficult to see k(u + v) = ku + kv where k is a scalar and u and v are vectors
Dot Product and Norm
The dot product or inner product of vectors u = (u1, u2, . . . , un) and v = (v1, v2, . . . , vn) is denoted by u.v and defined by
u.v = u1v1 + u2v2 + . . . + unvn
The norm or length of a vector, u, is denoted by ||u|| and defined by
Matrices
Matrix, A, means a rectangular array of numbers A = 
The m horizontal n-tuples are called the rows of A, and the n vertical m-tuples, its columns. Note that the element aij, called the ij-entry, appear in the ith row and the jthcolumn.
In algorithmic (study of algorithms), we like to write a matrix A as A(aij).
Column Vector
A matrix with only one column is called a column vector
Zero Matrix
A matrix whose entries are all zero is called a zero matrix and denoted by 0.
Matrix Addition
Let A and B be two matrices of the same size. The sum of A and B is written as A + B and obtained by adding corresponding elements from A and B.A+B =
=
Scalar Multiplication
The product of a scalar k and a matrix A, written kA or Ak, is the matrix obtained by multiplying each element of A by k. kA = k
= 
Here, we define -A = (-1)A and A - B = A + (-B). Note that -A is the negative of the matrix A.
Properties of Matrix under Addition and Multiplication
Let A, B, and C be matrices of same size and let k and l be scalars. Then
- (A + B) + A + (B + C)
- A + B = B + A
- A + 0 = 0 + A = A
- A + (-A) = (-A) + A = 0
- k(A + B) = kA + kB
- (k + l)A = kA + lA
- (kl)A = k(lA)
- lA = A
Matrix Multiplication
Suppose A and B are two matrices such that the number of columns of A is equal to number of rows of B. Say matrix A is an m×p matrix and matrix B is a p×n matrix. Then the product of A and B is the m×n matrix whose ij-entry is obtained by multiplying the elements of the ith row of a by the corresponding elements of the jth column of B and then adding them.It is important to note that if the number of columns of A is not equal to the number of rows of B, then the product AB is not defined.
Properties of Matrix Multiplication
Let A, B, and C be matrices and let k be a scalar. Then
- (AB)C = A(BC)
- A(B+C) = AB + AC
- (B+C)A = BA + CA
- k(AB) = (kB)B = A(kB)
Transpose
The transpose of a matrix A is obtained by writing the row of A, in order, as columns and denoted by AT. In other words, if A - (Aij), then B = (bij) is the transpose of A if bij - aji for all i and j.It is not hard to see that if A is an m×n matrix, then AT is an n×m matrix.
For example if A =
, then AT = 
Square Matrix
If the number of rows and the number of columns of any matrix are the same, we say matrix is a square matrix, i.e., a square matrix has same number of rows and columns. A square matrix with n rows and n columns is said to be order n and is called an n-square matrix.The main diagonal, or simply diagonal, of an n-square matrix A = (aij) consists of the elements a11, a22, a33, . . . , amn.
Unit Matrix
The n-square matrix with 1's along the main diagonal and 0's elsewhere is called the unit matrix and usually denoted by I.
Why unit matrix?
The unit matrix plays the same role in matrix multiplication as the number 1 does in the usual multiplication of numbers.
AI = IA = A
for any square matrix A.
So what dude?
We can form powers of a square matrix X by defining
X2 = XX
X3 = X2X, XXX, . . .
X0 = I
Big deal!
We can also form polynomial in X. That is, for any polynomial
f(x) = a0 + a1x + a2x2 + . . . + anxn
We define f(x) to be the matrix
f(x) = a0I + a1x + a2x2 + . . . + anxn
Note that in the case that f(A) is the zero matrix, then matrix A said to be a zero of the polynomial f(x) or a root of the polynomial equation f(x) = 0.
Now you're talking !!!!
Invertible Matrices
A square matrix A is said to be invertible if there exists a matrix B with the property AB = BA = I (Identity Matrix). Such a matrix B is unique and it is called the matrix of A and is denoted by A-1. Here, the important observation is that B is the inverse of A if and only if A is the matrix of B. It is known that AB = I if and only if BA = I; hence it is necessary to test only one product to determine whether two given matrices are inverse.Determinants
To each n-square matrix A = (aij), we assign a specific number called the determinants of A and denoted as|A| = del(A)
= 
where an n by n arrays of numbers enclosed by straight lines is called a determinant of order n. It is important to note that n by n array of numbers enclosed by straight line (see above) is NOT a matrix but denotes the number that the determinant function assigns to the enclosed array of numbers, i.e., the enclosed square matrix.
The determinant of order one is |a11| = a11
The determinant of order two is
= a11a22 - a12a21The determinant of order three is
= a11a22a32+ a12a23a31 + a13a21a32 - a13a22a31 - a12a21a33 - a11a23a32The determinant of order fo... You get the picture !
General Definition of Determinant
The general definition of a determinant of order n is as followsdet(A) = 
where the sum is over all possible permutations
= (j1, j2 , . . . , jn ) of (1, 2, . . . , n). Here sgn() equals plus or minus one according as an even or an odd number of interchanges are required to change so that its numbers are in the usual order.An important property of the determinant function is
Lemma. For any two n-square matrices A and B, det(AB) = det(A) . det(B).
In simple words the lemma say that the determinant function is multiplicative.
An important point in the context of invertible matrices and determinant is
Lemma. A square matrix is invertible if and only if it has a nonzero determinant.
A good news and a bad news: If you're an under graduate, you're done here! now goto CLR- If you're graduate and interested in theoretical Computer Science its time to go and find some good on matrix theory. (You'll need this shit for Linear Programming, for example).
Linear Inequalities and Linear Equations
Inequalities
The term inequality is applied to any statement involving one of the symbols <, >,
, 
.Example of inequalities are:
i. x1
ii. x + y + 2z > 16
iii. p2 + q2 1/2
iv. a2 + ab > 1
1 ii. x + y + 2z > 16
iii. p2 + q2
1/2iv. a2 + ab > 1
Fundamental Properties of Inequalities
1. If ab and c is any real number, then a + cb + c.
b and c is any real number, then a + cb + c.For example, -3
-1 implies -3+4-1 + 4.2. If a
b and c is positive, then acbc.For example, 2
3 implies 2(4) 3(4).3. If a
b and c is negative, then acbc.For example, 3
9 implies 3(-2)9(-2).4. If a
b and bc, then a c.For example, -1/2
2 and 28/3 imply -1/28/3.Solution of Inequality
By solution of the one variable inequality 2x + 37 we mean any number which substituted for x yields a true statement.For example, 1 is a solution of 2x + 3
7 since 2(1) + 3 = 5 and 5 is less than and equal to 7.By a solution of the two variable inequality x - y
5 we mean any ordered pair of numbers which when substituted for x and y, respectively, yields a true statement.For example, (2, 1) is a solution of x - y
5 because 2-1 = 1 and 15.By a solution of the three variable inequality 2x - y + z
3 we means an ordered triple of number which when substituted for x, y and z respectively, yields a true statement.For example, (2, 0, 1) is a solution of 2x - y + z
3.A solution of an inequality is said to satisfy the inequality. For example, (2, 1) is satisfy x - y
5.Two or more inequalities, each with the same variables, considered as a unit, are said to form a system of inequalities. For example,
x0
y0
2x + y4
Note that the notion of a system of inequalities is analogous to that of a solution of a system of equations. 0y
02x + y
4Any solution common to all of the inequalities of a system of inequalities is said to be a solution of that system of inequalities. A system of inequalities, each of whose members is linear, is said to be a system of linear inequalities.
Geometric Interpretation of Inequalities
An inequality in two variable x and y describes a region in the x-y plane (called its graph), namely, the set of all points whose coordinates satisfy the inequality.The y-axis divide, the xy-plane into two regions, called half-planes.
- Right half-plane
The region of points whose coordinates satisfy inequality x > 0. - Left half-plane
The region of points whose coordinates satisfy inequality x < 0.
- Upper half-plane
In which inequality y > 0 is true. - Lower half-plane
In which inequality y < 0 is true.
What is x-axis and y-axis? They are simply lines. So, the above arguments can be applied to any line.
Every line ax + by = c divides the xy-plane into two regions called its half-planes.
- On one half-plane ax + by > c is true.
- On the other half-plane ax + by < c is true.
Linear Equations
One Unknown
A linear equation in one unknown can always be stated into the standard formax = b
where x is an unknown and a and b are constants. If a is not equal to zero, this equation has a unique solution
x = b/a
Two Unknowns
A linear equation in two unknown, x and y, can be put into the formax + by = c
Solution of Linear Equation
A solution of the equation consists of a pair of number, u = (k1, k2), which satisfies the equation ax + by = c. Mathematically speaking, a solution consists of u = (k1, k2) such that ak1 + bk2 = c. Solution of the equation can be found by assigning arbitrary values to x and solving for y OR assigning arbitrary values to y and solving for x.
Geometrically, any solution u = (k1, k2) of the linear equation ax + by = c determine a point in the cartesian plane. Since a and b are not zero, the solution u correspond precisely to the points on a straight line.
Two Equations in the Two Unknowns
A system of two linear equations in the two unknowns x and y isa1x + b1x = c1
a2x + b2x = c2
a2x + b2x = c2
Where a1, a2, b1, b2 are not zero. A pair of numbers which satisfies both equations is called a simultaneous solution of the given equations or a solution of the system of equations.
Geometrically, there are three cases of a simultaneous solution
- If the system has exactly one solution, the graph of the linear equations intersect in one point.
- If the system has no solutions, the graphs of the linear equations are parallel.
- If the system has an infinite number of solutions, the graphs of the linear equations coincide.
The special cases (2) and (3) can only occur when the coefficient of x and y in the two linear equations are proportional.
OR => a1b2 - a2b1 = 0 => 
= 0
=> a1b2 - a2b1 = 0 => = 0The system has no solution when
The solution to system
a1x + b1x = c1
a2x + b2x = c2
can be obtained by the elimination process, whereby reduce the system to a single equation in only one unknown. This is accomplished by the following algorithma2x + b2x = c2
ALGORITHM
Step 1 Multiply the two equation by two numbers which are such that
the resulting coefficients of one of the unknown are negative of
each other.
Step 2 Add the equations obtained in Step 1.
The output of this algorithm is a linear equation in one unknown. This equation may be solved for that unknown, and the solution may be substituted in one of the original equations yielding the value of the other unknown.
As an example, consider the following system
3x + 2y = 8 ------------ (1)
2x - 5y = -1 ------------ (2)
2x - 5y = -1 ------------ (2)
Step 1: Multiply equation (1) by 2 and equation (2) by -3
6x + 4y = 16
-6x + 15y = 3
-6x + 15y = 3
Step 2: Add equations, output of Step 1
19y = 19
Thus, we obtain an equation involving only unknown y. we solve for y to obtain
y = 1
Next, we substitute y =1 in equation (1) to get
x = 2
Therefore, x = 2 and y = 1 is the unique solution to the system.
n Equations in n Unknowns
Now, consider a system of n linear equations in n unknowns
a11x1 + a12x2 + . . . + a1nxn = b1
a21x1 + a22x2 + . . . + a2nxn = b2
. . . . . . . . . . . . . . . . . . . . . . . . .
an1x1 + an2x2 + . . . + annxn = bn
a21x1 + a22x2 + . . . + a2nxn = b2
. . . . . . . . . . . . . . . . . . . . . . . . .
an1x1 + an2x2 + . . . + annxn = bn
Where the aij, bi are real numbers. The number aij is called the coefficient of xj in the ith equation, and the number bi is called the constant of the ith equation. A list of values for the unknowns,
x1 = k1, x2 = k2, . . . , xn = kn
or equivalently, a list of n numbers
u = (k1, k2, . . . , kn)
is called a solution of the system if, with kj substituted for xj, the left hand side of each equation in fact equals the right hand side.
The above system is equivalent to the matrix equation.
or, simply we can write A × = B, where A = (aij), × = (xi), and B = (bi).
The matrix
is called the coefficient matrix of the system of n linear equations in the system of n unknown.The matrix
is called the augmented matrix of n linear equations in n unknown.Note for algorithmic nerds: we store a system in the computer as its augmented matrix. Specifically, system is stored in computer as an N × (N+1) matrix array A, the augmented matrix array A, the augmented matrix of the system. Therefore, the constants b1, b2, . . . , bn are respectively stored as A1,N+1, A2,N+1, . . . , AN,N+1.
Solution of a Triangular System
If aij = 0 for i > j, then system of n linear equations in n unknown assumes the triangular form.
a11x1 + a12x2 + . . . + a1,n-1xn-1 + a1nxn = b1
a22x2 + . . . + a2,n-1xn-1 + a2nxn = b2
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
an-2,n-2xn-2 + an-2,n-1xn-1 + an-2,nxn-1 + a2nxn = b2
an-1,n-1xn-1 + an-1,nxn = bn-1 amnxn = bn
Where |A| = a11a22 . . . ann; If none of the diagonal entries a11,a22, . . ., ann is zero, the system has a unique solution.
Back Substitution Method
we obtain the solution of a triangular system by the technique of back substitution, consider the above general triangular system.
1. First, we solve the last equation for the last unknown, xn;
xn = bn/ann
2. Second, we substitute the value of xn in the next-to-last equation and solve it for the next-to-last unknown, xn-1:
.3. Third, we substitute these values for xn and xn-1 in the third-from-last equation and solve it for the third-from-last unknown, xn-2 :
.In general, we determine xk by substituting the previously obtained values of xn, xn-1, . . . , xk+1 in the kth equation.
. Gaussian Elimination
Gaussian elimination is a method used for finding the solution of a system of linear equations. This method consider of two parts.
- This part consists of step-by-step putting the system into triangular system.
- This part consists of solving the triangular system by back substitution.
x - 3y - 2z = 6 --- (1)
2x - 4y + 2z = 18 --- (2)
-3x + 8y + 9z = -9 --- (3)
2x - 4y + 2z = 18 --- (2)
-3x + 8y + 9z = -9 --- (3)
First Part
Eliminate first unknown x from the equations 2 and 3.
(a) multiply -2 to equation (1) and add it to equation (2). Equation (2) becomes
2y + 6z = 6
(b) Multiply 3 to equation (1) and add it to equation (3). Equation (3) becomes
-y + 3z = 9
And the original system is reduced to the system
x - 3y - 2z = 6
2y + 6z = 6
-y + 3z = 9
2y + 6z = 6
-y + 3z = 9
Now, we have to remove the second unknown, y, from new equation 3, using only the new equation 2 and 3 (above).
a, Multiply equation (2) by 1/2 and add it to equation (3). The equation (3) becomes 6z = 12.
Therefore, our given system of three linear equation of 3 unknown is reduced to the triangular system
x - 3y - 2z = 6
2y + 6z = 6
6z = 12
2y + 6z = 6
6z = 12
Second Part
In the second part, we solve the equation by back substitution and get x = 1, y = -3, z = 2
In the first stage of the algorithm, the coefficient of x in the first equation is called the pivot, and in the second stage of the algorithm, the coefficient of y in the second equation is the point. Clearly, the algorithm cannot work if either pivot is zero. In such a case one must interchange equation so that a pivot is not zero. In fact, if one would like to code this algorithm, then the greatest accuracy is attained when the pivot is as large in absolute value as possible. For example, we would like to interchange equation 1 and equation 2 in the original system in the above example before eliminating x from the second and third equation.
That is, first step of the algorithm transfer system as
2x - 4y + 2z = 18
x - 4y + 2z = 18
-3x + 8y + 9z = -9
x - 4y + 2z = 18
-3x + 8y + 9z = -9
Determinants and systems of linear equations
Consider a system of n linear equations in n unknowns. That is, for the following system
a11x1 + a12x2 + . . . + a1nxn = b1
a21x1 + a22x2 + . . . + a2nxn = b2
. . . . . . . . . . . . . . . . . . . . . . . . .
an1x1 + an2x2 + . . . + annxn = bn
a21x1 + a22x2 + . . . + a2nxn = b2
. . . . . . . . . . . . . . . . . . . . . . . . .
an1x1 + an2x2 + . . . + annxn = bn
Let D denote the determinant of the matrix A +(aij) of coefficients; that is, let D =|A|. Also, let Ni denote the determinants of the matrix obtained by replacing the ith column of A by the column of constants.
Theorem. If D
0, the above system of linear equations has the unique solution 
.This theorem is widely known as Cramer's rule. It is important to note that Gaussian elimination is usually much more efficient for solving systems of linear equations than is the use of determinants.
0 comments