Vector spaces involving square matrices

Question

Friends! Do you know some interesting vector spaces involving square matrices? I'm trying to do my first research work in coding theory, and I plan it to be related to square matrices. Thank you. :)

Answer 1

Let $A\in\mathbb{R}^{n\times n}$ be a nonsymmetric and nonsingular matrix with zero/nonzero element structure that has nonzero elements on the main diagonal, i.e., $\alpha_{i,j}\neq 0$, the first superdiagonal, i.e., $\alpha_{i,i+1}\neq 0$, the first subdiagonal, i.e., $\alpha_{i-1,i}\neq 0$, the fourth superdiagonal, i.e., $\alpha_{i,i+4}\neq 0$, and the fourth subdiagonal, i.e., $\alpha_{i-4,i}\neq 0$. For $n = 15$ this has the form $$ A = \begin{pmatrix} * & * & 0 & 0 & * & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ * & * & * & 0 & 0 & * & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & * & * & * & 0 & 0 & * & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & * & * & * & 0 & 0 & * & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ * & 0 & 0 & * & * & * & 0 & 0 & * & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & * & 0 & 0 & * & * & * & 0 & 0 & * & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & * & 0 & 0 & * & * & * & 0 & 0 & * & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & * & 0 & 0 & * & * & * & 0 & 0 & * & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & * & 0 & 0 & * & * & * & 0 & 0 & * & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & * & 0 & 0 & * & * & * & 0 & 0 & * & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & * & 0 & 0 & * & * & * & 0 & 0 & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & * & 0 & 0 & * & * & * & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & * & 0 & 0 & * & * & * & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & * & 0 & 0 & * & * & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & * & 0 & 0 & * & * \\ \end{pmatrix} $$ Your task is to implement a factorization routine that given $A$ in a suitably efficient data structure returns the factors $L$ and $U$ where $L$ is unit lower triangular and $U$ is upper triangular. In order to guarantee that pivoting is not required you may restrict $A$ to be a diagonally dominant matrix. You must also write routines that solve systems $Lv = f$ and $Uv = f$ for arbitary vectors $v$ and $f$ and $L$ and $U$ matrices that result from your factorization routine. Your code must be as efficient as possible in terms of the number of comptuations and the storage required. Your solution must include:

1. A discussion of the structure of the factors $L$ and $U$.

2. A description of your factorization algorithm and triangular system solving algorithms.

3. A derivation of the computational complexity of your algorithms.

4. A description and justification for an efficient data structure to hold A and to return $L$ and $U$. Be specific about your data structure’s characteristics and how you access elements in the data structure that correspond to specific elements in $A$, $L$ and $U$.

5. A discussion of the design of the experiments to verify the code works correctly. Be specific about the metrics used to assess the results generated by the code and the way you generate examples.

6. A discussion of the nonzero patterns of $L$ and $U$ if partial pivoting (in a column) was introduced to the algorithm and how it would affect your data structure. You do not have to implement pivoting.