I noticed a similarity between matrix multiplication and the map and reduce functions of functional programming languages.
Define a "functional matrix multiplication" operation, x, by a pair of binary operators, + and *. The operation x allows two matrices U and V to be multiplied, denoted U x V, using + and * in place of addition and multiplication. Let's let + be evaluated in a right associative fashion (although a left associative version is also possible). + is also associated with a zero element, used in the same fashion as the default value of reduce.
Establishing the types: Let A be the set of matrices m by n matrices with values of type T and B be the set of n by o matrices with values of type S, and let C and D be arbitrary types. Let E be the set of m by o matrices with values of type D.
x has type A->B->E
+ has type C->D->D
* has type S->T->C
For example:
Mapping a sequence S by a function f consists of taking the product of f viewed as a 1x1 matrix, with the sequence viewed as a row vector, where * is "apply" and + is anything. i.e., f x S^t (where ^t takes the transpose)
Reducing a sequence S by a function g consists of taking the dot product of the sequence with a sequence I whose elements are all the identity function, where * is "apply" and + is g. i.e., I^t x S
Zipping a sequence S with another sequence T consists of taking the dot product of the two sequences, where * is "cons" and + is also "cons."
But the interesting thing is that this allows one to generalize map and reduce operations to work on matrices that are not just column vectors (sequences)! And the matrix on the left doesn't just have to have elements that are functions, and they don't have to be all the same function. Finally, this allows one to consider the meaning of other operations on matrices such as the determinant.
One example from mathematics: the del operator, which sums the partial derivatives of a vector function, is considered as a matrix only as a "notational convenience," with the product being purely formal. But in this framework, applying del to a vector function v is really a "functional matrix multiplication" del x v, where + is function addition, 0 is the zero function, and * is apply.
Define a "functional matrix multiplication" operation, x, by a pair of binary operators, + and *. The operation x allows two matrices U and V to be multiplied, denoted U x V, using + and * in place of addition and multiplication. Let's let + be evaluated in a right associative fashion (although a left associative version is also possible). + is also associated with a zero element, used in the same fashion as the default value of reduce.
Establishing the types: Let A be the set of matrices m by n matrices with values of type T and B be the set of n by o matrices with values of type S, and let C and D be arbitrary types. Let E be the set of m by o matrices with values of type D.
x has type A->B->E
+ has type C->D->D
* has type S->T->C
For example:
Mapping a sequence S by a function f consists of taking the product of f viewed as a 1x1 matrix, with the sequence viewed as a row vector, where * is "apply" and + is anything. i.e., f x S^t (where ^t takes the transpose)
Reducing a sequence S by a function g consists of taking the dot product of the sequence with a sequence I whose elements are all the identity function, where * is "apply" and + is g. i.e., I^t x S
Zipping a sequence S with another sequence T consists of taking the dot product of the two sequences, where * is "cons" and + is also "cons."
But the interesting thing is that this allows one to generalize map and reduce operations to work on matrices that are not just column vectors (sequences)! And the matrix on the left doesn't just have to have elements that are functions, and they don't have to be all the same function. Finally, this allows one to consider the meaning of other operations on matrices such as the determinant.
One example from mathematics: the del operator, which sums the partial derivatives of a vector function, is considered as a matrix only as a "notational convenience," with the product being purely formal. But in this framework, applying del to a vector function v is really a "functional matrix multiplication" del x v, where + is function addition, 0 is the zero function, and * is apply.
© Bart Parkis
Last modified:Tue May 19 19:07:52 2009