这个Assignment是使用R语言开发一种用于处理矩阵问题的工具包
MATH 4370 / MATH 7370 Fall 2019
Coding assignment 2 (CA2)
The aim of the coding assignments is to develop a toolkit for dealing with matrix problems. Here are some remarks and instructions regarding coding assignments. Please read these instructions carefully, as I will remove points if you do not follow them.
• This assignment is the same for students registered in both versions of the course.
• Coding assignments CA1–CA3 can be submitted in any order.
• There is no specific due date for this assignment, but there are constraints:
1. CA4 can only be submitted once CA1–CA3 have also been submitted. (All 4 could be submitted concurrently.)
2. CA4 is due no later than Sunday 1 December at 23:59.
3. You must have submitted at least 2 coding assignments by 8 November at 23:59.
• Use R or MatLab/Octave.
• The submission of this assignment can consist of two parts:
1. an R or MatLab/Octave file containing all the functions;
2. an optional companion PDF file with extended documentation of the functions produced, stating explicitly the definitions and theorems used, etc. If you comment your code abundantly, then the companion file should not be required if no further mathematical developments are needed. Your companion file, if any, should be in PDF format.
• The functions must be named, take arguments and return results exactly as prescribed here. In order for you to check that this is indeed the case, use the provided driver script (CA2 driver.R or CA2 driver.m) to test your code.
Given a matrix M ∈ Mmn, each function should first ensure that the matrix has the proper size (e.g., be square if the definition involves a square matrix). Until CA4, we do not implement proper error handling,so for now, if the matrix is not of the proper size, the function should return FALSE.
Diagonalisation
We admit (i.e., no need to code them, you can use them as is) the R function eigen and the MatLab/Octave function eig, which return a list with elements values and vectors containing, respectively, the eigenvalues and eigenvectors of a real or complex matrix M ∈ Mmn. The following functions should be made available.
1. improved eigen(M) improves on the R function for computing eigenvalues and eigenvectors. It returns four elements instead of two:
(a) values lists the eigenvalues. Eigenvalues with algebraic multiplicity strictly larger than 1 are only listed once.
(b) vectors lists the eigenvectors corresponding to each eigenvalue. Vectors are normalised and, if they are entry-wise nonnegative or nonpositive, are given as nonnegative vectors.
(c) alg mult gives the algebraic multiplicity of each eigenvalue.
(d) geom mult gives the geometric multiplicity of each eigenvalue. [Note that this is typically not a problem you will be able to solve properly using simple programming. Do the best you can.]
2. is defective(M) returns TRUE if M is defective, FALSE if M is nondefective.
3. is derogatory(M) returns TRUE if M is derogatory, FALSE if M is nonderogatory.
4. is diagonalizable(M) returns TRUE if M is diagonalizable, FALSE otherwise.
5. diagonalize(M) returns FALSE if M is not diagonalizable. If M is diagonalizable, it returns D, the diagonalized form of M, and S, the similarity transformation matrix that puts M in diagonal form.
Block structure
Here is an interesting challenge. Write code that detects block diagonal or block triangular structure in matrices. The following functions should be provided:
6. is block diagonal(M) returns TRUE if M is block diagonal, FALSE otherwise.
7. is block upper triangular(M) returns TRUE if M is block upper triangular, FALSE otherwise.
8. is block lower triangular(M) returns TRUE if M is block lower triangular, FALSE otherwise.
9. is block triangular(M) returns TRUE if M is block triangular, FALSE otherwise.
10. is block tridiagonal(M) returns TRUE if M is block tridiagonal, FALSE otherwise. (This is the hardest. It is a bonus question.)
Here is a hint. (I will discuss the block diagonal case; the block triangular case works the same way but is a little harder. So I recommend that you start with the block diagonal case. As indicated, characterising block tridiagonality is hardest and is a bonus question.) You will need to extract submatrices, distinguishing diagonal ones, which, in a block diagonal matrix, can be anything, and off-diagonal ones, which must be all zero. So it is probably a good idea to implement a function is zero matrix(M) to test whether a matrix is a zero matrix. Then work your way either up or down the number of possible blocks.
Suppose for instance you have a 5 × 5 matrix. If it is block diagonal, this means it has either 2, 3 or 4 diagonal blocks. If it is block diagonal with 5 diagonal blocks, then it is actually diagonal and should be identified as such (using the function in CA1). The case of 1 block is also vacuous, because in this case we are just thinking about the entire matrix.
In terms of determining whether our 5 × 5 matrix has block diagonal structure, it is equivalent to start by considering whether it has 2 blocks or 4 blocks. However, suppose we want to do more processing once we know if the matrix is block diagonal. It is then in our interest to have more blocks; indeed, suppose our matrix takes the form
a11 a12 0 0 0
0 a22 0 0 0
0 0 a33 a34 0
0 0 a43 a44 0
0 0 0 0 a55
There are multiple ways to split this matrix into a block diagonal matrix. However, the most useful one in general is the one that identifies the following blocks:
a11 a12
0 a22,
a33 a34
a43 a44
and
a55.
So I would recommend starting from the highest possible number of blocks and making your way down.
Remember that for block matrices, the partitions of rows and columns have to be sequential, so that possible partitions of indices into 4 subsets is quite simple here:
{1}, {2}, {3}, {4, 5}
{1}, {2}, {3, 4}, {5}
{1}, {2, 3}, {4}, {5}
{1, 2}, {3}, {4}, {5}.
Start with the first partition. If all off-diagonal blocks are zero, you can stop: the matrix is indeed block diagonal. Otherwise, test the second, etc. If when you have exhausted all partitions, you still have not detected block-diagonality, proceed the same way but now looking for 3 blocks instead of 4. This time, there are more sequential partitions of indices:
{1}, {2}, {3, 4, 5}
{1}, {2, 3, 4}, {5}
{1, 2, 3}, {4}, {5}
{1}, {2, 3}, {4, 5}
{1, 2}, {3}, {4, 5}
{1, 2}, {3, 4}, {5}.
(In the example matrix given above, that last partition would work.) If these are exhausted, look for two blocks:
{1}, {2, 3, 4, 5}
{1, 2, 3, 4}, {5}
{1, 2, 3}, {4, 5}
{1, 2}, {3, 4, 5}.
(In the example above, both {{1, 2, 3, 4}, {5}} and {{1, 2}, {3, 4, 5}} would work.)
In terms of implementation, because this is what is called an embarrassingly parallel problem, I would recommend first generating the entire list of all possible partitions, then using it