PLEASE Help Me this is chain multiplication problem 1 should

PLEASE Help Me. this is chain multiplication problem.

?=-1 should be an eigenvalue of multiplicity 5.

B) Write out all possible chain structures. using the appropriate solution space and it’s dimension, identify which structure is correct

Fill in the blanks: the solution space you are using for this is S_n where n=__. Dim S_n = __. Circle or identify by label the correct chain structure.

Solution

The chain matrix multiplication problem is perhaps the most popular example of dynamic programming used in the upper undergraduate course (or review basic issues of dynamic programming in advanced algorithm\'s class).

The chain matrix multiplication problem involves the question of determining the optimal sequence for performing a series of operations. This general class of problem is important in complier design for code optimization and in databases for query optimization. We will study the problem in a very restricted instance, where the dynamic programming issues are clear. Suppose that our problem is to multiply a chain of n matrices A₁A₂ ... A_n. Recall (from your discrete structures course), matrix multiplication is an associative but not a commutative operation. This means that you are free to parenthesize the above multiplication however we like, but we are not free to rearrange the order of the matrices. Also, recall that when two (non-square) matrices are being multiplied, there are restrictions on the dimensions.

Suppose, matrix A has p rows and q columns i.e., the dimension of matrix A is p × q. You can multiply a matrix A of p × q dimensions times a matrix B of dimensions q × r, and the result will be a matrix C with dimensions p × r. That is, you can multiply two matrices if they are compatible: the number of columns of A must equal the number of rows of B.

In particular, for 1 i   p and 1 j r, we have

C[i, j] = _{1 k q}A[i, k] B[k, j].

There are p . r total entries in C and each takes O(q) time to compute, thus the total time to multiply these two matrices is dominated by the number of scalar multiplication, which is p .q . r.

Given a sequence of n matrices A₁, A₂, ... A_n, and their dimensions p₀, p₁, p₂, ..., p_n, where where i = 1, 2, ..., n, matrix A_i has dimension p_{i 1} × p_i, determine the order of multiplication that minimizes the the number of scalar multiplications.

Equivalent formulation (perhaps more easy to work with!)

Given n matrices, A₁, A₂, ... A_n, where for 1 i n, A_i is a p_{i 1} × p_i, matrix, parenthesize the product A₁, A₂, ... A_n so as to minimize the total cost, assuming that the cost of multiplying an p_{i 1}× p_i matrix by a p_i × p_{i + 1} matrix using the naive algorithm is p_{i 1}× p_i × p_{i + 1}.