0
$\begingroup$

I would like to determine the sparsity pattern of a matrix $A_m$, where the entry $(k,l)$ of $A_m$ is non-zero if the condition $\operatorname{test}(k,l,m)$ is true:

$\operatorname{test}(k,l,m)$ = "The sum $k+l+m$ is even ($mod(k+l+m,2)=0$) and the sum of any two integers is not smaller that the third one (i.e. $k+l \geq m$ and $k+m \geq l$ and $l+m \geq k$)."

Note that $q(k,l,m)$ is invariant by permutation of its entries.

For a given $m$, can we determine in advance the sparsity pattern of $A_m$ without looping over all the entries?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

This post was originally just intended to display an image of the sparsity pattern for $A_{20}$, which I include at the end.

But to address the OP's comment below this post, I realize I'm a little confused as to what a "formula" means in this context. If we take that to mean "produce a list of the non-zero values", then consider the following piece of pseudo-code (where in our figure, we would take $m=20, n=60$):

for i in {0,1,2,...,n-1}
   s = max(0, i-n+m+1)
   for j in {s,s+1,..., m-s}
      row = m + i - j
      col = i + j

I believe this process will enumerate all the non-zero entries once without repetition.

Note that I have used "0-up" indexing, i.e., I treat the first entry of the matrix as "row 0, column 0" instead of "row 1, column 1"; converting to 1-up indexing should be straightforward.

In any event, here's the figure:

A matrix with a rotated checkboard-like pattern

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thakn you for the plot, it was definitely missing. For a given $m$, and a matrix dimension $N \times N$ (here $N = 60$), can we get a formula for all the indices (k,l) in black? $\endgroup$
    – Mathieu le provost
    Commented Aug 16, 2023 at 1:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .