The Classic Multiplication Algorithm

An algorithm is a set of rules for carrying out calculation either by hand or on a machine.
An algorithm is a finite step-by-step procedure to achieve a required result.
An algorithm is a sequence of computational steps that transform the input into the output.
An algorithm is a sequence of operations performed on data that have to be organized in data structures.
An algorithm is an abstraction of a program to be executed on a physical machine (model of Computation).
The most famous algorithm in history dates well before the time of the ancient Greeks: this is Euclid's algorithm for calculating the greatest common divisor of two integers.
The Classic Multiplication Algorithm
1. Multiplication, the American way:
Multiply the multiplicand one after another by each digit of the multiplier taken from right to left.
2. Multiplication, the English way:
Multiply the multiplicand one after another by each digit of the multiplier taken from left to right.

Algorithmic is a branch of computer science that consists of designing and analyzing computer algorithms
The “design” pertain to
The description of algorithm at an abstract level by means of a pseudo language, and
Proof of correctness that is, the algorithm solves the given problem in all cases.
The “analysis” deals with performance evaluation (complexity analysis).
We start with defining the model of computation, which is usually the Random Access Machine (RAM) model, but other models of computations can be use such as PRAM. Once the model of computation has been defined, an algorithm can be describe using a simple language (or pseudo language) whose syntax is close to programming language such as C or java.

Algorithm's Performance
Two important ways to characterize the effectiveness of an algorithm are its space complexity and time complexity. Time complexity of an algorithm concerns determining an expression of the number of steps needed as a function of the problem size. Since the step count measure is somewhat coarse, one does not aim at obtaining an exact step count. Instead, one attempts only to get asymptotic bounds on the step count. Asymptotic analysis makes use of the O (Big Oh) notation. Two other notational constructs used by computer scientists in the analysis of algorithms are Θ (Big Theta) notation and Ω (Big Omega) notation.The performance evaluation of an algorithm is obtained by totaling the number of occurrences of each operation when running the algorithm. The performance of an algorithm is evaluated as a function of the input size n and is to be considered modulo a multiplicative constant.
The following notations are commonly use notations in performance analysis and used to characterize the complexity of an algorithm.
Θ-Notation (Same order)
This notation bounds a function to within constant factors. We say f(n) = Θ(g(n)) if there exist positive constants n0, c1 and c2 such that to the right of n0 the value of f(n) always lies between c1g(n) and c2g(n) inclusive.



O-Notation (Upper Bound)
This notation gives an upper bound for a function to within a constant factor. We write f(n) = O(g(n)) if there are positive constants n0 and c such that to the right of n0, the value of f(n) always lies on or below cg(n).




Ω-Notation (Lower Bound)
This notation gives a lower bound for a function to within a constant factor. We write f(n) = Ω(g(n)) if there are positive constants n0 and c such that to the right of n0, the value of f(n) always lies on or above cg(n).


Algorithm Analysis
The complexity of an algorithm is a function g(n) that gives the upper bound of the number of operation (or running time) performed by an algorithm when the input size is n.
There are two interpretations of upper bound.
Worst-case Complexity
The running time for any given size input will be lower than the upper bound except possibly for some values of the input where the maximum is reached.
Average-case Complexity
The running time for any given size input will be the average number of operations over all problem instances for a given size.
Because, it is quite difficult to estimate the statistical behavior of the input, most of the time we content ourselves to a worst case behavior. Most of the time, the complexity of g(n) is approximated by its family o(f(n)) where f(n) is one of the following functions. n (linear complexity), log n (logarithmic complexity), na where a≥2 (polynomial complexity), an (exponential complexity).

Optimality
Once the complexity of an algorithm has been estimated, the question arises whether this algorithm is optimal. An algorithm for a given problem is optimal if its complexity reaches the lower bound over all the algorithms solving this problem. For example, any algorithm solving “the intersection of n segments” problem will execute at least n2 operations in the worst case even if it does nothing but print the output. This is abbreviated by saying that the problem has Ω(n2) complexity. If one finds an O(n2) algorithm that solve this problem, it will be optimal and of complexity Θ(n2).

Reduction
Another technique for estimating the complexity of a problem is the transformation of problems, also called problem reduction. As an example, suppose we know a lower bound for a problem A, and that we would like to estimate a lower bound for a problem B. If we can transform A into B by a transformation step whose cost is less than that for solving A, then B has the same bound as A.
The Convex hull problem nicely illustrates "reduction" technique. A lower bound of Convex-hull problem established by reducing the sorting problem (complexity: Θ(nlogn)) to the Convex hull problem.




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 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 CardinalityThe 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 a one-to-one correspondence. It is easy to see that the cardinality of an empty set is zero i.e., . MustiestIf 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 {}. SubsetFor 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 if
x A implies x B
written
x A => x B.
Proper SubsetSet 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 SetsThe 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 SetLet 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 SetsLet A and B be sets. A and B are disjoint if A B = .Union of SetsThe 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,
A B = { x : x A or x B}.
For two finite sets A and B, we have identity
A B = A + B - AB
We can conclude
A B A + B
That is,
if A B = 0 then A B = A + B and if A B then A B
Intersection SetsThe intersection of set set A and B, written AB, is the set of elements that are both in A and in B. That is,
AB = { x : x A and x B}.
Partition of SetA 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 = .
ii. Their union is S, that is, S = Si
In other words, S form a partition of S if each element of S appears in exactly on Si.Difference of SetsLet A and B be sets. The difference of A and B is
A - B = {x : x 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 SetAll 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}.
For any set A U, we have following laws
i. A'' = Aii. A A' = .iii. A A' = U
Symmetric 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}

Therefore,

A B = (A B) - (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}.SequencesA 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}.TuplesFinite 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 ProductIf 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}.
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-tuplesThe 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}
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 = An 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 vectorsDot Product and NormThe 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 jth column.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 MultiplicationLet 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 MultiplicationLet 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 = a11The 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 follows
det(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 isLemma. 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 <, >, , =" type="#_x0000_t75">. Example of inequalities are:
i. x=" type="#_x0000_t75"> 1 ii. x + y + 2z > 16 iii. p2 + q2 1/2iv. 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=" type="#_x0000_t75"> bc.
For example, 3 9 implies 3(-2)=" type="#_x0000_t75"> 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=" type="#_x0000_t75"> 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=" type="#_x0000_t75"> 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=" type="#_x0000_t75"> 0 y=" type="#_x0000_t75"> 02x + y=" type="#_x0000_t75"> 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-planeThe region of points whose coordinates satisfy inequality x > 0.
Left half-planeThe region of points whose coordinates satisfy inequality x < 0.
Similarly, the x-axis divides the xy-plane into two half-planes.
Upper half-planeIn which inequality y > 0 is true.
Lower half-planeIn 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 EquationA 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 = c1a2x + 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
The system has no solution when The solution to system
a1x + b1x = c1a2x + 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 = b1a21x1 + 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 = bnWhere 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)
First PartEliminate 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 equationsConsider 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 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.