Sum the diagonals of a matrix

xeon123 · 05-07-2012, 05:14 AM

If I have a matrix of nxm, I want to sum the values in the diagonal of the matrix. My problem is slightly different from calculate the determinant.

Here is an example:

| 1 2 3 4 6 7 |
| 8 9 1 2 3 4 |
| 5 6 7 8 9 1 |
| 2 3 4 5 6 7 |

I want to calculate the sum of each diagonal. For example:
v1 = 1+9+7+5
v2 = 2+1+8+6
v3 = 3+2+9+7
v4 = 4+3+1
v5 = 6+4
v6 = 7
v8 = 8+6+4
v9 = 5+3
v10 = 2

How do I solve this problem? It doesn't matter the programming language that I'm using. Can anyone give me an idea?

johnsfine · 05-07-2012, 06:14 AM

I assume zero based indexing, but that depends on the language.

1) Initialize the sums to zero. There should be Rows+Cols-1 sums
2) Iterate over the source matrix in any convenient sequence, hitting each r,c (row and column intersection) exactly once.
2a) Compute which sum it belongs to:
index = c-r
if (index<0) index=Cols-index-1
2b) Add to the correct sum
S[index] += M[r,c]

Notice that I chose a source oriented algorithm: Deal with the source values in any convenient sequence, and for each source value figure out which destination position(s) it goes to.
A destination oriented algorithm usually is closer to the original problem statement: For each destination position, go through all the source positions needed to compute that destination.
Part of learning to program is learning to make good choices between alternate approaches like that. In this case, the source oriented algorithm has only one complicated detail (adjusting the index for the case that the simplistic index is negative). But a destination oriented algorithm has more than one complication.
In serious programming, you often need to focus on performance consequences rather than just simplicity in such choices. In this case, that drives the decision the same way: The big source and small destination means that (if the matrix were big enough for performance to matter) cache coherent access to the source is more important than cache coherent access to the destination.

onebuck · 05-07-2012, 06:17 AM

Moved: This thread is more suitable in <Programming> and has been moved accordingly to help your thread/question get the exposure it deserves.

danielbmartin · 05-07-2012, 08:39 AM

Quote:

Originally Posted by xeon123

Can anyone give me an idea?

The product of a fevered imagination...

Starting with this ...

Code:

1 2 3 4 6 7 
8 9 1 2 3 4 
5 6 7 8 9 1 
2 3 4 5 6 7

... "twist" the matrix to produce this ...

Code:

      1 2 3 4 6 7
    8 9 1 2 3 4
  5 6 7 8 9 1
2 3 4 5 6 7

Summing the columns produces the nine desired numeric results but not in the same sequence.

Daniel B. Martin

danielbmartin · 05-11-2012, 09:40 AM

Quote:

Originally Posted by xeon123

I want to calculate the sum of each diagonal. ...
How do I solve this problem?

First thing: determine the dimensions of the matrix.

Code:

rows=$(wc -l < $InFile)
echo; echo "rows =" $rows

cols=$(head -1 $InFile | wc -w)
echo "columns =" $cols

diags=$(($rows+$cols-1))
echo "diagonals =" $diags

Starting with this matrix...

Code:

1 2 3 4 6 7 
8 9 1 2 3 4 
5 6 7 8 9 1 
2 3 4 5 6 7

... extend it to the right with three columns of zeroes. Why three? It is the number of rows, minus one. Then replicate the original matrix on the right of this "padded with zeroes" version. This awk builds Workfile 1 ...

Code:

awk -F " " '{printf $0; for (i=0; i<'$rows-1'; i++) printf "0 "; printf $0; printf "\n"}' $InFile > $Work1

... which looks like this ...

Code:

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

Now use another awk to "twist" this interesting stretched matrix and save it in Workfile 2.

Code:

awk -F " " '{for (i=NR; i<=NF; i++) printf $i " "; printf "\n"}' $Work1 > $Work2

Workfile 2 looks like this ...

Code:

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

Use a third awk to sum the columns, remembering that we need only the left-most nine values.

Code:

awk -F " "  '{for(i=1;i<='$diags';i++){sum[i]+=$i;}} END         \
   {OFS=" "; for(i=1;i<=NF;i++) printf sum[i] " "; printf "\n"}' $Work2 > $OutFile

The finished product, nine sums, are written to an output file. They look like this:

Code:

22 17 21 8 10 7 2 8 18

Having done this step-by-step and writing interim results to work files allows us to visualize the process and debug as necessary. When confident that the code is working properly the three steps may be combined into one pipe, eliminating the need for work files. The pipe looks like this:

Code:

 awk -F " " '{printf $0; for (i=0; i<'$rows-1'; i++) printf "0 "; printf $0; printf "\n"}' $InFile \
|awk -F " " '{for (i=NR; i<=NF; i++) printf $i " "; printf "\n"}'                                  \
|awk -F " " '{for(i=1;i<='$diags';i++){sum[i]+=$i;}} END                                           \
   {OFS=" "; for(i=1;i<=NF;i++) printf sum[i] " "; printf "\n"}' > $OutFile

I am a beginner with awk and realize this may be clumsy code. Experienced LQers are invited to polish it and show us a better method.

Daniel B. Martin

danielbmartin · 05-11-2012, 09:45 AM

Quote:

Originally Posted by xeon123

I want to sum the values in the diagonal of the matrix. ...
It doesn't matter the programming language that I'm using.

As a side note, I think a solution to this problem could be written in one line of APL. I don't have an APL interpreter for Linux. Is one available?

Daniel B. Martin

millgates · 05-11-2012, 11:36 AM

This could be done in a single awk command (based on johnsfine's algorithm):

Code:

awk '{ for(i=1;i<=NF;i++)a[i-NR]+=$i }
END {
    m=NR-1 ;n=m+NF; for(i=0;i<n;i++)printf "%i %s",a[(i+m)%n-m],i==n-1?"\n":" "
}'< $infile > $outfile

If you don't insist on that particular order of sums, this might be slightly shorter:

Code:

awk '{for (i=1;i<=NF;i++)a[i-NR]+=$i} END {for(i=-NR+1;i<=NF;i++)printf "%s %s",a[i],i==NF?"\n":" "}'< $infile $outfile

johnsfine · 05-11-2012, 11:51 AM

Quote:

Originally Posted by millgates

This could be done in a single awk command

I haven't tested your awk command to see what I might be missing, but I can't see the reordering could work. You use
(i+m)%n-m
So the direction (as i increases) is positive on both sides of the wrap point.
As I understood the original request, the specified sequence through the simplistic diagonal numbers is negative on the other side of the wrap point.

millgates · 05-11-2012, 12:07 PM

Oh, sorry. I was comparing my output with Daniel's output in post #5 instead of the original post.

This should work better:

Code:

awk '{for(i=1;i<=NF;i++)a[i-NR]+=$i}END{n=NR+NF-1;for(i=0;i<n;i++)printf "%i %s",a[i>=NF?-i+NF-1:i],i==n-1?"\n":" "}'

amani · 05-11-2012, 12:12 PM

It is best done in R

If tp is a matrix with 3 rows 4 columns

then

sum(diag(tp[,-3]))

will give the diagonal sum after deleting 3rd column

markush · 05-11-2012, 04:49 PM

Hi,

Quote:

Originally Posted by danielbmartin

As a side note, I think a solution to this problem could be written in one line of APL. I don't have an APL interpreter for Linux. Is one available?

Daniel B. Martin

at least there are binaries for the J-language here http://www.jsoftware.com/stable.htm

Markus

grail · 05-12-2012, 03:45 AM

Using millgates example, here is a slight variation:

Code:

awk '{c=1;for(i=1;i<=NF;i++)a[(n=NR+NF-i) > NF?n:c++]+=$i}END{for(i=1;i<NF+NR;i++)print a[i]}' file

You can change the print to the printf solution if you prefer on one line with spaces.

millgates · 05-12-2012, 05:36 AM

Quote:

Originally Posted by grail

Using millgates example, here is a slight variation:

Code:

awk '{c=1;for(i=1;i<=NF;i++)a[(n=NR+NF-i) > NF?n:c++]+=$i}END{for(i=1;i<NF+NR;i++)print a[i]}' file

You can change the print to the printf solution if you prefer on one line with spaces.

Still can get slightly shorter

))

Code:

awk '{for(i=0;i++<NF;)a[(c=i-NR)<0?NF-c:c+1]+=$i}END{for(;++j<NF+NR;)print a[j]}' file

ntubski · 05-12-2012, 10:22 PM

Quote:

Originally Posted by danielbmartin

As a side note, I think a solution to this problem could be written in one line of APL. I don't have an APL interpreter for Linux. Is one available?

Daniel B. Martin

J is APL derivative using ASCII characters. Here is a solution in J (input in bold):

Code:

   mat =: 4 6 $ 1 2 3 4 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7
   mat
1 2 3 4 6 7
8 9 1 2 3 4
5 6 7 8 9 1
2 3 4 5 6 7
   +//.|."1 mat
7 10 8 21 17 22 18 8 2

The "literate" version (execution is right to left):

Code:

   require '/usr/local/j64-602/system/packages/misc/primitiv.ijs'
   sum =: + insert
   eachrow =: rank 1
   (sum oblique) (reverse eachrow) mat
7 10 8 21 17 22 18 8 2