Basic bibliography by r

Basic bibliography by Kris

A-Z

Dartboard challenge solved - learn about matrices and circular series

posted Nov 15, 2012, 6:55 AM by roberto mensa   [ updated Nov 15, 2012, 6:58 AM ]
You can read about the challenge itself here:
Sum of the squares of each k consecutive terms in the dartboard sequence
First it was published here (italian):
[Quizzone di Excel] Quesito 10
The challenge was posted on Linkedin a year later:
Excel Hero Group on Linkedin

To download the sample files at the bottom of the page by clicking on the small arrow on the right-hand side.

First solution

The task was to sum of the squares of each k consecutive terms in the dartboard numbering sequence - that means you need to create the k-element groups following the circle or in other words, combine the first and last elements (circular shift).
The best and generalized solution is a result of a long and entertaining discussion on this forum. Final and best formula is:

=SUM(MMULT((ROW(rng)<=TRANSPOSE(ROW(rng)))*(ROW(rng)>TRANSPOSE(ROW(rng))-k)+(ROW(rng)>ROWS(rng)+TRANSPOSE(ROW(rng))-k),rng)^2)

The importance of this formula is that it solves the base problem: how to shift k-element groups of an array regarding the fact that we need circular shift .
Note: In the examples - to make the matrixes smaller - we will use numbers from 1 to 10.
When you are thinking on the solution, it could be a great help to write the numbers in a 10x10 matrix, not in 3 column - something like this for the k=3 case:



In the rows of the 10x10 matrix you can see the k-element groups we need to sum and square. The bottom-left elements are the key to create the circular shift. Now we need to build up a help-matrix which will make possible to do this shift on the original range.
If you think about the rules of matrix multiplication, you find out this is what you need:



How can you build up this shift-matrix? You only need to use the row and column index numbers and combine two simple matrixes.
We set:
rng =
A2:A11 (assume, for simplicity, the values ​​from 1 to 10)
k = 3


Highlight
the individual operations with different colors:

=SUM(MMULT((ROW(rng)<=TRANSPOSE(ROW(rng)))*(ROW(rng)>TRANSPOSE(ROW(rng))-k)+(ROW(rng)>ROWS(rng)+TRANSPOSE(ROW(rng))-k),rng)^2)

Below what happens:



Second solution

We found two other solutions which are not as general as the above mentioned, but could also be interesting.

The second solution is based how we calculate square of sum of elements.
Here is the formula:

=SUM(((ABS(ROW(rng)-TRANSPOSE(ROW(rng)))<k)*(k-ABS(ROW(rng)-TRANSPOSE(ROW(rng))))+(ABS(ROW(rng)-TRANSPOSE(ROW(rng)))>ROWS(rng)-k)*(ABS(ROW(rng)-TRANSPOSE(ROW(rng)))-ROWS(rng)+k))*(rng*TRANSPOSE(rng)))


Let’s see how the squares look like for k=3:


We have 3 times the square of the element (c), 2*2 times the multiplication with the element above (b) and 2*2 times the element below (d) and 2*1 times the multiplication with the element two-places above and below (a, e).
In Excel if we multiply the vector and its transposed vector we will have the multiplication of all the possible combination of two elements. (aa, ab, ac, … | ba, bb, bc, ...) We only need to “select” which combinations we need and how many times. This latter will be a coefficient-matrix depends on the value of k.
We created an example file to explain how to build up the coefficient matrix. It is a little bit similar to the method we used in the general solution. The difference is that in this case we need a symmetrical matrix, so we need to use ABS formula.


Third solution

The third solution uses the fact that we have integer numbers. (This is not an “elegant” mathematical solution but a “smart” algorithmic solution. :) )
Here is the formula:

=SUM(MMULT((SMALL(rng/100+MOD(ROW(rng),ROWS(rng)),MOD(ROW(rng)+COLUMN(OFFSET(A1,,,,k)),
ROWS(rng))+1)-(MOD(ROW(rng)+COLUMN(OFFSET(A1,,,,k)),ROWS(rng))))*100,ROW(OFFSET(A1,,,k))^0)^2)

Because the key of the calculation is the order of the numbers, the idea is to “combine” the number and its serial number together. We can add them together after dividing the number by 100 - this way the integer part will be the serial number while the fractional part will be the number itself. Now we can easily read the k-element groups with the help of an array of serial numbers and the SMALL function.


We will only need the fractional part, so we subtract the array of serial numbers and multiply the fractional part by 100. And only two things left: summarize the rows of this matrix (matrix-multiplication by the sum-vector), square it and summarize again.

Words: Kris by FrankensTeam
Solutions: Kris, Plinius, r
Č
Ĉ
ď
roberto mensa,
Nov 15, 2012, 6:55 AM
Ĉ
ď
roberto mensa,
Nov 15, 2012, 6:55 AM
Ĉ
ď
roberto mensa,
Nov 15, 2012, 6:55 AM
Comments