0
$\begingroup$

I was wondering if there is a formula to find the sum of all the items in a matrix. The value at each index is (column $XOR$ row). For example, a matrix with 5 rows and 8 columns would be 

0 1 2 3 4 5 6 7
1 0 3 2 5 4 7 6
2 3 0 1 6 7 4 5
3 2 1 0 7 6 5 4
4 5 6 7 0 1 2 3

I also need to take away a fixed amount from each of the items in the matrix (keeping each item 0 or above). Making the grid I need to find the sum of:

0 0 1 2 3 4 5 6
0 0 2 1 4 3 6 5
1 2 0 0 5 6 3 4
2 1 0 0 6 5 4 3
3 4 5 6 0 0 1 2
$\endgroup$
7
  • $\begingroup$ Every row is a permutation of the numbers $0$ through $7$, which sum to $28$, so with $5$ rows that's $140$ total. (Btw. a row is left to right, a column top to bottom .. so what you showed has 5 rows and 8 columns) ... Now, can you elaborate on what you need to do with that matrix? $\endgroup$
    – Bram28
    Commented Dec 18, 2017 at 20:11
  • $\begingroup$ Sum all the values in the matrix (after subtracting 1 (or any number) from each item in the matrix.) With this example, the sum should be 105, however I have a matrix with $28827050410$ columns and $35165045587$ rows and going through each item would take a long time! $\endgroup$
    – Joseph
    Commented Dec 18, 2017 at 20:19
  • $\begingroup$ You mean $100$ in your example, right? Since there are $40$ entries ... Oh, I see, you don;t subtract the $1$ from $0$, is that it? OK, but with that huge matrix: do you know anything about that matrix? That is, are the rows nice permutations of certain numbers as in your example? Or are the entries just totally random numbers? $\endgroup$
    – Bram28
    Commented Dec 18, 2017 at 20:20
  • $\begingroup$ Yeah, if you take 1 and it is less than 0 you set the value to 0. $\endgroup$
    – Joseph
    Commented Dec 18, 2017 at 20:23
  • $\begingroup$ Where's your own workings on the problem? You've not even provided sufficient information in your post to be answerable. $\endgroup$
    – amWhy
    Commented Dec 18, 2017 at 20:24

1 Answer 1

Reset to default
0
$\begingroup$

So ... you have rows numbered $0$ through $35165045587-1=35165045586$, and columns numbered $0$ through $28827050410-1=28827050409$, and the entry at $(x,y)$ is defined as $x \ XOR \ y$ with the $XOR$ defined as an operator on the two numbers written as binary strings.

OK, well, then since you have fewer rows than columns, each column will contain some permutation of the numbers $0$ through $35165045586$ (I'll leave that to you to rigorously prove, but think about how the XOR operation works) meaning that the numbers in each column add up to $$\frac{35165045586\cdot 35165045587}{2}$$ and thus the sum of all entries in the matrix equals:

$$\frac{28827050410\cdot 35165045586\cdot 35165045587}{2}$$

Now, can you figure out how this sum changes when you subtract $k$ from each entry, making it $0$ when it threatens to go below $0$? You saw how it works for $k=1$ ... so now consider what happens when $k=2$ ... and at that point you should see the pattern and should be able to put that in a formula.

$\endgroup$
1
  • $\begingroup$ it's only true when the number of columns is a power of 2. For example, calculate a 3*6 matrix, you'll see that the 3rd row will have the elements [ 2 3 0 1 6 7]; You can see that this row has a '7' in it (on the right most column). Adding up the numbers won't give a sum of 1...5, which your formula is basing on this assumption - that each row will have a permutation of [0,M-1], where M is the number of columns. But it seems to me that this observation of yours gives at least 1/3 of the solution. $\endgroup$
    – Elyasaf755
    Commented May 26, 2022 at 15:26

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