Mathematics for Algorithmic

Posted by Laxman on 2:17 AM in , , | 0 comments
      
















  1. Mathematics for Algorithmic
    • Sets
    • Vectors and Matrices
    • Linear Inequalities and Linear Equations    


Sets

  A set is a collection of different things (distinguishable objects or distinct objects) represented as a unit. The objects in a set are called its elements or members. If an object x is a member of a set S, we write x belongs to S. On the the hand, if x is not a member of S, we write z does not belong to 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 belongs to {7, 21, 57} and 8 does not belong to {7, 21, 57} or equivalently, 7 belongs to S and 8 does not belong to 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 belongs to 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., |Phi| .


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 Phior {}.


Subset

For two sets A and B, we say that A is a subset of B, written A Subset of B, if every member of A also is a member of B.

Formally, A Subset of B if
x belongs to A implies x belongs to B
written
 
x belongs to A => x belongs to B.

Proper Subset

Set A is a proper subset of B, written A Proper subset of B, if A is a subset of B and not equal to B. That is,  A set A is proper subset of B if ASubset of B but A not equal to 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 ASubset of B and BSubset of 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 Subset of 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  AUnionB = Phi.


Union of Sets

The union of A and B, written AUnion B, is the set we get by combining all elements in A and B into a single set. That is,
AUnionB = { x : x belongs to A or  x belongs to B}.

For two finite sets A and B, we have identity
|AUnionB| = |A| + |B| - |AIntersectionB|

We can conclude
|AUnionB| less than or equal to |A| + |B|

That is, 
if |AUnionB| = 0 then |AUnionB| = |A| + |B| and if A Subset of B then |A| less than or equal to |B|



Intersection Sets

The intersection of set set A and B, written AIntersectionB, is the set of elements that are both in A and in B. That is,
AIntersectionB =  { x : x belongs to A and  x belongs to 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 belongs to and i not equal j imply Si Intersection Sj = Phi.
ii. Their union is S, that is, S = Union Si

In 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 belongs to A  and   x does not belong to 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 belongs to U  and   x does not belong to A}.

For any set A Subset of U, we have following laws
i.   A'' = A
ii.  A Intersection A' = Phi.
iii. A Union A' = U

Symmetric difference 

Let A and B be sets. The symmetric difference of A and B is
Asymmetic difference B = { x : x belongs to A or  x belongs to B but not both}

Therefore,

Asymmetic difference B = (AUnionB) -  (AIntersectionB) 

As an example, consider the following two sets A = {1, 2, 3} and B = {2, 4, 6, 8}. The symmetric difference, Asymmetic differenceB = {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) not equal {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

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 belongs to A, b belongs to 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 belongs to 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
  1. (A + B) + A + (B + C)
  2. A + B = B + A
  3. A + 0 = 0 + A = A
  4. A + (-A) = (-A) + A = 0
  5. k(A + B) = kA + kB
  6. (k + l)A = kA + lA
  7. (kl)A = k(lA)
  8. 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
  1. (AB)C = A(BC)
  2. A(B+C) = AB + AC
  3. (B+C)A = BA + CA
  4. 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 - a12a21
The determinant of order three is     = a11a22a32+ a12a23a31 + a13a21a32 - a13a22a31 - a12a21a33 - a11a23a32
The determinant of order fo... You get the picture !


General Definition of Determinant

The general definition of  a determinant of order n is as follows
det(A) = 

where the sum is over all possible permutations sigma = (j1, j2 , . . . , jn ) of (1, 2, . . . , n). Here sgn(sigma) equals plus or minus one according as an even or an odd number of interchanges are required to change sigma 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.       x>=1 
ii.      x + y + 2z > 16 
iii.     p2 + q2 =< 1/2
iv.     a2 + ab > 1

Fundamental Properties of Inequalities

1.    If a=<b and c is any real number, then a + c=<b + c.

                            For example, -3=<-1 implies -3+4=<-1 + 4.

2.    If a=<b and c is positive, then ac=<bc.

                            For example, 2=<3 implies 2(4) =< 3(4).

3.    If a=<b and c is negative, then ac>=bc.

                            For example, 3=<9 implies 3(-2)>=9(-2).

4.    If a=<b and b=<c, then a=< c.

                            For example, -1/2=<2 and 2=<8/3 imply -1/2=<8/3.


    Solution of Inequality

    By solution of the one variable inequality 2x + 3=<7 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 1=<5.


    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,
            x>=0
            y>=0
    2x + y>=4
    Note that the notion of a system of inequalities is analogous to that of a solution of a system of equations. 

    Any 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.
    Similarly, the x-axis divides the xy-plane into two half-planes.
    • 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 form
    ax = 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 form
    ax + by = c

    where  x and y are two unknowns and a, b, c are real numbers. Also, we assume that a and b are no zero.



    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 is
    a1x + b1x = c1
    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
    1. If the system has exactly one solution, the graph of the linear equations intersect in one point.
    2. If  the system has no solutions, the graphs of the linear equations are parallel.
    3. 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.
    a_1/a_2 = b_1/b_2

    OR  a_1/a_2 = b_1/b_2   =>  a1b2 - a2b1 = 0    =>  = 0

    The 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 algorithm

    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)

    Step 1: Multiply equation (1) by 2 and equation (2) by -3
     6x + 4y = 16
    -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

    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 =   b    n
    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.
    1. This part consists of step-by-step putting the system into triangular system.
    2. 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)

    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


    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

    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




    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


    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 Dnot equal 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.



     



    Tags: , ,

    Laxman Singh

    0 comments

    Leave a Reply

    Newer Post Older Post Home
    Related Posts Plugin for WordPress, Blogger...