5. In computer science, the complexity of an algorithm is (roughly) computed by

Question

5. In computer science, the complexity of an algorithm is (roughly) computed by counting the number of times a given operation is performed. Suppose adding or subtracting any two numbers takes a seconds, and multiplying two numbers takes m seconds. Then, for example, computing 2·65 would take a + m seconds. (a) How many additions and multiplications does it take to compute the determinant of a general 2×2 matrix? (b) Write a formula for the number of additions and multiplications it takes to compute the determinant of a general n×n matrix using the denition of the determinant as a sum over permutations. Assume that nding and multiplying by the sign of a permutation is free. For part b, find how many operations it takes to compute the determinant of an n × n matrix using the co-factor expansion.

Explanation / Answer

a)calculation of determinant of a general 2 * 2 matrix

let us taken a 2*2 matrix that is a b

c d

forumula for determinant is = ad-bc

so in this formule 2 multifications and 1 addition is there.

b) formula for determinat of n*n matrix is

The number of parts with non-zero determinants was 2 in the 2 by 2 case, 6 in the 3 by 3 case, and will be 24 = 4! in the 4 by 4 case. This is because there are n ways to choose an element from the first row (i.e. a value for ), after which there are only n 1 ways to choose an element from the second row that avoids a zero determinant. Then there are n 2 choices from the third row, n 3 from the fourth, and so on. The big formula for computing the determinant of any square matrix is: det A = ±a1a2a3...an n! terms where (, , , ...) is some permutation of (1, 2, 3, ..., n). If we test this on the identity matrix, we find that all the terms are zero except the one corresponding to the trivial permutation = 1, = 2, ..., = n. This agrees with the first property: det I = 1. It’s possible to check all the other properties as well, but we won’t do that here. Applying the method of elimination and multiplying the diagonal entries of the result (the pivots) is another good way to find the determinant of a matrix.

The cofactor formula rewrites the big formula for the determinant of an n by n matrix in terms of the determinants of smaller matrices.

in the 3 × 3 case, the formula looks like

: det A = a11(a22a33 a23a32) + a12(a21a33 + a23a31) + a13(a21a32 a22a31)

This comes from grouping all the multiples of aij in the big formula. Each element is multiplied by the cofactors in the parentheses following it. Note that each cofactor is (plus or minus) the determinant of a two by two matrix. That each cofactor is (plus or minus) the determinant of a two by two matrix. That determinant is made up of products of elements in the rows and columns NOT containing a1j. In general, the cofactor Cij of aij can be found by looking at all the terms in the big formula that contain aij. Cij equals (1)i+j times the determinant of the n 1 by n 1 square matrix obtained by removing row i and column j. (Cij is positive if i + j is even and negative if i + j is odd.) For n × n matrices, the cofactor formula is: det A = a11C11 + a12C12 + · · · + a1nC1n.

Applying this to a 2 × 2 matrix gives us: a b = ad + b(c).

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.