Jump to content
  • Advertisement
Sign in to follow this  
mathematical

Matrix Major and multiplication

This topic is 991 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Given the formula for matrix multiplication:

matrix-properties142.png

 

Does the interpretation of this change with row / column major? I assume not, but i'm not 100% sure.

 

The way i interpret the above formula is:

Element (i, j) of Matrix AB is equal to the dot product of Row I from Matrix A and Column J from Matrix B

 

I assume that given the matrix:

A B
C D

Element 0, 1 in row major would be B

Element 0, 1 in column major would be C

This makes sense, after all to convert from row to column major is just a transpose.

 

So, following the above formula, multiplying these Matrices:

E F * I J
G H   K L

Row Major element 0, 1 (B) = E * J + F * L

Column Major  element 0, 1 (C) = E * J + F * L

 

The same value just in a transposed position. But this is where my confusion kicks in. Should the subscript interpretation dictate if something is a row or column? For example:

Row Major 0, 1 = Row 0, Column 1, Dot(Row 0, Colum 1)

Column Major 0, 1 = Column 0, Row 1, Dot (Column 0, Row 1)

 

OR, does the interpretation stay row / column no matter what? (That's the real question of this thread)

Row Major 0, 1 = Row 0, Column 1, Dot(Row 0, Colum 1)

Column Major 0, 1 = Column 0, Row 1, Dot(Row 0, Colum 1)

 

I think the second one makes sense, where the order stays Row / Column no matter what. It seems to make sense, considering the result will be the same matrix for both majors just transposed for one.

 

Is that correct?

Share this post


Link to post
Share on other sites
Advertisement
The mathematical definition of matrix multiplication stays the same, regardless of the conventions you use.

Note that there's two different "majorness" conventions that you have to choose:
*Mathematical row/column majorness. This basically means, in a transformation matrix, do you store the basis vectors in the rows or columns. This choice affects whether you'll use C=A*B or C=B*A, when working out your concatenation math. i.e. you don't change the multiplication function itself, but you do change how it is used.
*computer science row/column majorness. This is the 1D array storage order, e.g. given:
A B
C D
do you store it in memory as (rows) ABCD, or (columns) ACBD? This decision has no bearing on the math at all, it's just an implementation detail inside the 2D-array-lookup operator/accessor.

It's possible to mix anf match and combination of those two conventions.

Share this post


Link to post
Share on other sites


The way i interpret the above formula is:

Element (i, j) of Matrix AB is equal to the dot product of Row I from Matrix A and Column J from Matrix B

No, the formula stays in-tact without you having interpreted i and j respectively, as columns/rows, or, rows/columns.

The formula is explicit only about relation of arbitrary 2d and 2d, it can take any dimensions as prior literaly.

Share this post


Link to post
Share on other sites

Thanks guys! That really cleared things up!

 

@Hodgman, i have a followup question regarding this statement:

*Mathematical row/column majorness. This basically means, in a transformation matrix, do you store the basis vectors in the rows or columns. This choice affects whether you'll use C=A*B or C=B*A, when working out your concatenation math. i.e. you don't change the multiplication function itself, but you do change how it is used.

 

The question has nothing to do with multiplying matrices, just on the subscripts used to access them.

 

So, Mathematically, a row major matrix would be:

Xx Xy Xz 0
Yx Yy Yz 0
Zx Zy Zz 0
Tx Ty Tz 1

And a column major matrix would be:

Xx Yx Zx Tx
Xy Yy Zy Ty
Xz Yz Zz Tz
0  0  0  1

With X, Y, Z being the basis vectors and T being a transform component.

 

I assume that the subscript is interpreted differently:

Row Major: Element (2, 1) is in row 2, column 1 which would be Zy

Column Major: Element (2, 1) is in column 2, row 1 which would again be Zy

 

The first element in the accessor is the row for row major matrices

The first element in the accessor is the column for column major matrices

So, apart from where the basis vectors are stored, when accessing elements the subscripts are interpreter differently

 

My question is Mathematically, is that correct? 

 

OR Would the subscripting stay the same and element 2, 1 be Zy in the row major matrix and the same element 2, 1 be Yz in the column major matrix?

Edited by mathematical

Share this post


Link to post
Share on other sites

I assume that the subscript is interpreted differently:
...
OR Would the subscripting stay the same

Nope - the latter is true; subscripts are independent of what you're using the matrix for. That's a property of the matrix itself, which doesn't care what data is inside it. You could have a 4x4 square matrix that somehow stores probabilities of finding gum under seats, but the "names" of the grid cells inside that square array stay the same as always.

Share this post


Link to post
Share on other sites

In that case, mathematically is subscript Mij always interpreted as the i-th column and j-th row of Matrix M?

Regardless of the major of the matrix?

 

BTW, Thanks for putting up with all these questions.

Share this post


Link to post
Share on other sites


In that case, mathematically is subscript Mij always interpreted as the i-th column and j-th row of Matrix M?

Regardless of the major of the matrix?

 

It is very common to see [row][column] instead of [column][row] indexing, but that does not have much to do with majorness, as the termines row and column are not defined in linear algebra, the majorness equivalently relates to how matricies transform vectors, but commonly column is the base/space vector.

 

Since matrix is an ordered set of vectors, you should specify the vectors in it, this way you have no doubt how to transform vectors with it, thus what matrix it actually is.

Share this post


Link to post
Share on other sites

Sorry guys, a lot of this confusion seems to stem from my lack of formal math understanding.

 

@JohnnyCode, i think what you are saying is

A row major matrix is an array of row vectors and a column major matrix is an array of column vectors.

So, element (i, j) of a matrix should be considered the j-th element of the i-th vector in the matrix.

 

This would entail, indexing elements in a row major matrix would look like

00 01 02
10 11 12
20 21 22

And indexing elements in a column major matrix would look like

00 10 20
01 11 21
02 12 22

So if i want to multiply these two matrices (M1, M2)

A B C   K L M
D E F * N O P
H I J   Q R S

If we where in row major, element 0, 2 (row 0, column 2) of M1 would be C

If we where in column major, element 0, 2 (column 0, row 2) of the M1 would H

 

The multiplication in row major (M1 * M2) would be

A * K + B * N + C * Q,  A * L + B * O + C * R,  A * M + B * P + C * S
D * K + E * N + F * Q,  D * L + E * O + F * R,  D * L + E * O + F * R
H * K + I * N + K * Q,  H * L + I * O + K * R,  H * L + I * O + K * R

Which could also be written as:

M1(row0) DOT M2(col0), M1(row0) DOT M2(col1), M1(row0) DOT M2(col2)
M1(row1) DOT M2(col0), M1(row1) DOT M2(col1), M1(row1) DOT M2(col2)
M1(row2) DOT M2(col0), M1(row2) DOT M2(col1), M1(row2) DOT M2(col2)

And the same multiplication (in the same order) (A * B) in column major would be:

A * K + B * N + C * Q,  D * K + E * N + F * Q,  H * K + I * N + K * Q
A * L + B * O + C * R,  D * L + E * O + F * R,  H * L + I * O + K * R
A * M + B * P + C * S,  D * L + E * O + F * R,  H * L + I * O + K * R

Which could be written as:

M1(row0) DOT M2(col0), M1(row1) DOT M2(col0), M1(row2) DOT M2(col0)
M1(row0) DOT M2(col1), M1(row1) DOT M2(col1), M1(row2) DOT M2(col1)
M1(row0) DOT M2(col2), M1(row1) DOT M2(col2), M1(row2) DOT M2(col2)

One is the transpose of the other, which i guess is what i would expect.

So, did i get it? Or am i still missing something here? Is the above math / reasoning correct?

Edited by mathematical

Share this post


Link to post
Share on other sites

In that case, mathematically is subscript Mij always interpreted as the i-th column and j-th row of Matrix M?

Regardless of the major of the matrix?

Rows and columns only exist in your mind.

They don't exist in math, they don't exist in computers (not entirely true, but for now, assume it).

 

We like to structure information, so we invented rows and columns, as it helps us think in higher level structures. If you look careful though, you'll see they don't really exist. (Or rather, you can choose to ignore them, and everything still works.)

 

An author may say Mij is a matrix, and then picks either i or j as row. That is however just the author creating structure for us. (Mathematicians tend to use the first index as row, computer scientists tend to take the first index as column, I guess we are more horizontally oriented tongue.png )

 

While the author may use words like row or column, in the math "code" itself however, there is no row or column, just M and 2 indices. Its meaning is that for every unique combination of i and j, you have a unique value Mij. It doesn't matter if you see columns, rows, separate variables, or whatever. Each unique combination of i and j gives a unique Mij, that is all it says.

 

It means that M11, M12, M21, and M22 are all different values. It's like

int p1, p2, p3, p4;

in your mind, you may see "p" here as a row or a column, but it's just 4 different variables, conveniently numbered, as I am too lazy to write

int loop, bar, catchy, fred;

there is no row, just 4 variables, written by a lazy programmer.

 

 

On to computer systems.

 

If you use a programming language other than assembly language for programming, chances are that it supports multi-dimensional arrays in some form, eg "int foo[5][6];". The same as above holds here. The compiler handles memory allocation for you. It also handles making sure that "foo[1][2]" gives you a unique value different from all values "foo[x][y] where x != 1 or y != 2". You can see "foo" like the "M" variable in math, just a lot of unique variables, conveniently numbered to save you the effort of inventing unique names for them.

 

You are free to interpret "foo" as just 30 separate variables, as 5 rows and 6 columns, as 6 rows of 5 columns, as an array of arrays holding 6 integers, and many other interpretations. As long as you keep in mind foo[a] == foo[x][y] if a==x and b==y, any interpretation you want to have works.

 

 

So where does row-major and column-major comes in then?

 

The problem in computers is that memory is not paper. Computer memory is completely linear, first byte is at address 0, last byte around address 340282366920938463463374607431768211455 (for a 32 bit system). In other words, memory is one VERY long row in memory (like "byte mem[340282366920938463463374607431768211456]"). As a result, only 1-dimensional arrays actually exist

  • , like

    int bar[30]

    The question is now how to fit "foo[5][6]" onto that array? The compiler just made us believe "foo[5][6]" exists.

     

    There are 2 common solutions in use:  foo[j] == bar[i + j*5] or foo[j] == bar[j + i*6]. This is what the compiler of your programming language is actually doing. You write foo[j], and the compiler then translates that to access in the "bar[x]" array.

    As you can see, while you can interpret rows and columns in "foo", they actually don't exist. It's all flattened to one long linear array, since that's the only way the computer allows storage.

     

    Now, by convention, my first solution is called column-major, and my second solution is called row-major. The reason is that mathematicians made the first computers, and thus saw "i" as "row" in their mind. "major" just means "when you increment this index, you make a big jump in memory".

    "row-major" thus means "make a big jump in memory if the first index changes".

     

    While sometimes you may want to care about the above foo -> bar mapping done by the compiler (see below), but you can also choose to ignore it. Everything will still work.

     

     

    And there you have the entire story. Bottom line is

    1. you can think in rows and columns as you want, as long as you do it consistently. Any interpretation will work (including my idea that rows and columns only exist in your mind), as long as you use the same interpretation consistently.

    2. Secondly, row-major and column-major is completely irrelevant, until

     

    - You want to implement multi-dimensional arrays in your compiler

    - You want to use the "bar[30]" interpretation at the same time as the "foo[5][6]" interpretation (eg when loading data from a file)

    - You are in a hurry, and want to control when you make big jumps in memory.

     

     

    Footnote:

  • Actually, an "int" is bigger than a byte, so bar[0] needs more than one memory address. The foo -> bar mapping is thus  foo[j] uses memory[base_of_bar + (i + j*5)*4] to memory[... + 3].

    Edited by Alberth

    Share this post


    Link to post
    Share on other sites

    Sorry  for the double post, but I felt it better making this point separately from my wall of text above.

     

     

     

    One is the transpose of the other, which i guess is what i would expect.

    So, did i get it? Or am i still missing something here? Is the above math / reasoning correct?

    As I tried explaining above, it doesn't matter what you do. Either solution works, as long as you use rows and columns consistently. So pick one index as row, and the other one as column, and use that everywhere.

     

    Edit: The reason this works is that your result will also be interpreted under those rules.

    Edited by Alberth

    Share this post


    Link to post
    Share on other sites
    Sign in to follow this  

    • Advertisement
    ×

    Important Information

    By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

    We are the game development community.

    Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

    Sign me up!