Straight forward algorithm for obtaining a sub matrix

Question

Ok so I just started writing a linear algebra toolbox in C++ for some other projects I have / plan on starting in the future.

So I define a matrix as the fundamental building block and vectors, scalars are just 1xn / nx1 and 1x1 matrices respectively.

Next, the matrix can be iterated through column wise such that, for example, if the matrix is $\begin{pmatrix} a & b \\ c & d \end{pmatrix}$, then the iterator would traverse the 1D array $\begin{bmatrix} a & b & c & d \end{bmatrix}$ linearly starting at $a$.

Ok, so just basic traversal so far nothing interesting. The next natural stepping stone is being able to subset a matrix such that any sub matrix which maintains element order can be obtained. So for example, if I have the following matrix:

$$ \begin{pmatrix} a & b & c & d \\ e & f & g & h \\ i & j & k & l \\ m & n & o & p \end{pmatrix} $$

and a function ${\it sub\_matrix(x, y)}$, then ${\it sub\_matrix(1,2)}$ would return the 3 x 3 matrix:

$$ \begin{pmatrix}a & b & d \\ i & j & l \\ m & n & p \end{pmatrix} $$

Where you can imagine the function $x=1$ "cutting through" the row $\begin{pmatrix} e & f & g & h\end{pmatrix}$ and $y=2$ cutting through the column $\begin{pmatrix} c & g & k & o\end{pmatrix}^{T}$. Ok so we can produce all ordered $(n-1)\times(n-1)$ submatries of the original matrix this way. Moreover, if $x < 0$ and $y \ge 0$, then we can obtain all ordered $n \times (n-1)$ matrices and all $(n-1) \times n$ for $y < 0$ and $x \ge 0$.

Ok so this is a great starting point, and is easily implemented $O(n)$. So if we leave it at this, then obtaining successively smaller sub matrices would require $O(n^{k})$ so not great. Instead, we can introduce some new parameters: ${left\_of}$, ${right\_of}$, ${above}$, and ${below}$ as inputs to ${\it sub\_matrix}$. So now, if we execute for example:

$${\it sub\_matrix(1,\,2,\, left\_of=1,\,right\_of=0,\,above=0,\,below=0)}$$

on the same original matrix, we would obtain $\begin{pmatrix} d & l & p \end{pmatrix}^{T}$ and:

$${\it sub\_matrix(1,\,2,\, left\_of=0,\,right\_of=1,\,above=1,\,below=0)}$$

would produce the matrix:

$$\begin{pmatrix}i & j \\ m & n\end{pmatrix}$$

Where the parameters ${(left\,/\,right)\_of}$ have the effect of excluding columns to the left of or the right of $x$ and $above$ and $below$ exclude rows above and below $y$.

Ok so now we can obtain many more of the ordered sub matrices in $O(n)$. Yay!!

${\bf\text{This is where I currently am in the problem}}$. Everything above here is already implemented and works well. The problem is that we still cannot extract inner sub matrices like $\begin{pmatrix} b & f & j & n \end{pmatrix}^{T}$ or $\begin{pmatrix} f & g \end{pmatrix}$ without applying this method successively.

My next thought is to introduce an $inversion$ parameter which would have the effect of choosing the elements on the lines $x$ and $y$ rather than the elements which aren't. The reason I didn't go ahead and do that is because the syntax is already starting to feel a bit clunky and I wanted to take a step back and get some thoughts from others.

I also want to mention that I do not have any formal education in computer science. My degree is in electrical engineering so although I have some of CS fundamentals, I may get lost if your explanation is not dumbed down enough lol. Also, if I am being braindead and there is a much more elegant way to do this then you can call me a brick and show me lmao I sometimes have the tendency to miss the obvious.

Anyways thanks!

Answer 1

Some approaches that can be used for this are mask arrays and index arrays.

Mask arrays: A mask array is just an array of boolean values. We can use two mask arrays to indicate which rows and which columns should be kept in the resulting submatrix. The code is something like this: So, for example, for your matrix submatrix(row_mask = [false, true, true, false], col_mask = [true, false, false, true]) will give $\begin{bmatrix}e & h \\ i & l\end{bmatrix}$. Note that it is easy to construct masks that correspond to submatrices you already can extract.

In order to save some memory, you can even make mask an abstract class and make subclasses that do not store a boolean array but compute in on the fly, for example, for "true for indices from $i_{0}$ to $i_1$ except $j$".

Index arrays: index array is an array of integers which will just contain indices of rows and columns we need to take. For example, submatrix(rows = [1, 2], cols = [0,3]) will again give $\begin{bmatrix}e & h \\i & l\end{bmatrix}$. As a bonus, you can have non-sorted index arrays or index arrays with duplicate entries to permute or duplicate rows and columns of your submatrix.