Find Array Mapping Homework Solution

[atrus_ovis]

Homework Statement

I don't know if this has ties to linear algebra, so sorry in advance if I'm posting in a wrong section.

We have an n*n matrix A, n is an odd number, and "the matrix's sides are 0" meaning:
we'll call non-zero elements as 1's for now.1st line 1111...1111
2nd line 0111...1110
3rd line 0011...1100
...
...
n-2 00111..11100
(n-1) 01111...1110
n 1111...1111
the diagonals are intact.

For example for n=3, this would be the matrix
111
010
111

for n=5

11111
01110
00100
01110
11111

etc

Now, the problem states that all non-zero data are stored in a 1-D array row by row, B[N-1], where N-1 the total number of nonzero elements(array index starts at 0).
We are asked to a)find a formula to correlate a non-zero element's coordinates in A with its position (array index) in array B.
For example for n=3, for the matrix A:

abc
0d0
efg

B would be b=[a,b,c,d,e,f,g], each non-zero elemet's position in B 0,1...6 respectively, and each nonzero element's coordinates {0,0}{0,1}{0,2}{1,1}{2,0}{2,1}{2,2} respectively.

and b) find a formula for the number of non-zero elements in A.

Homework Equations

?

The Attempt at a Solution

I found b), as
[Sum {from 1 to (n div 2)} 4*n ] + n , where div is integer division

as for a), i am trying to find a relation between i,j values, and their position in B, by trial and error, with only error so far.Any ideas?

 

[Mark44]

I don't think your formula for b is right. If n = 3, there are 7 nonzero elements. Your formula says there will be 12 + 3 = 15 such elements.

If n = 5, your formula gives 20 + 20 + 5 = 45, while there are in fact 17 nonzero elements.

Here's a formula that does work: n + (n - 2) + (n - 4) + ... + 3 + 1 + 3 + ... + (n - 4) + (n - 2) + n.

That's the same as 2[n + (n - 2) + (n - 4) + ... + 3] + 1. You might be able to rearrange that to a closed form summation.

Also, since n is odd, n + 1 is even, and the middle is at (n + 1)/2, which will always be an integer when n is odd.

The other part is harder, as you have found. To map the numbers in the one-d array to a pair of indexes in the two-d array, you have to figure out where you are in the one-d array. For example, for the 3 x 3 matrix, there are 7 nonzero elements, so your one-d array has 7 elements. You can think of them as being in three groups of size 3, 1, and 3, respectively. Everything in the first group comes from the first row (row 0) of the two-d array, and the number in the middle comes from the middle row of the two-d array, and the numbers in the last group come from the last row (row 2) of the two-d array. If you can figure out the mapping from element 0 through element (n + 1)/2 in the one-d array back to the two-d array, it should be pretty easy figuring out the mapping for the other half of the one-d array.

 

[atrus_ovis]

In my formula n is incrementing from 1 to n div 2 and only the 4*n part is summed. (sorry but i always make a mess when trying to write in LaTex)
it's [SUM(n=1 to n= ndiv2) {4*n} ] +n
for n=3 we have
(4*1 ) + 3 = 7
n=5
(4*1+4*2) + 5= 4+8+5=17

n=7
(4*1+4*2+4*3)+7=4+8+12+7=31.
etc

I had thought about the strategy you suggest, but i considered it too hard.
You made it clear though, I'll give it a shot .

 

[Mark44]

You have 4n in your summation - it should be 4i.

Here's the summation in LaTeX:
$$\left(\sum_{i = 1}^{(n + 1)/2} 4i\right) + n$$

 

[Mark44]

I had thought about the strategy you suggest, but i considered it too hard.
You made it clear though, I'll give it a shot .

That was the only way I could think of...

 

[atrus_ovis]

Yes,yes okay.

If you can figure out the mapping from element 0 through element (n + 1)/2 in the one-d array back to the two-d array, it should be pretty easy figuring out the mapping for the other half of the one-d array.

Ironically, i found out the summation up to (n+1)/2, but i can't find the rest.Heh.

1st row: i+j
2nd row: (n-1)*i +j
3rd row: (n-2)*i+j
4th row: (n-3)*i +j

up to the middle, where i=j, where it's the same pattern, up to (n-ndiv2+1)*i + j
tested it up to n=9,and it works
but for the bottom half rows, no pattern seems to work

edit:

last row: (ndiv2+1)*i + j
2nd to last (ndiv2)*(i+1)+j

 

[Mark44]

The 2nd half is symmetric to the 1st half. Maybe start from the end and work back to the middle.

 

[atrus_ovis]

The matrix is, the values of B aren't.

 

[Mark44]

No, the values of B are symmetric. Think about the 5x5 case. The B matrix has 17 entries: 5 for the first row, 3 for the second, 1 for the third, 3 for the fourth, and five for the fifth. Whichever of the groups a number is in corresponds to which row from the A matrix, and the position in the group corresponds to the column in that row.

 

[atrus_ovis]

I understand what you're saying - there is symmetry in B,corresponding to A's structure- but the whole issue here is to map the values of i,j to those values in B.
Which will work for any n.

It's just hard i guess.