How does the cartesian product relate to other products?
Moderators: gmalivuk, Moderators General, Prelates
How does the cartesian product relate to other products?
So I'm a computer science undergrad and am currently learning about matrix multiplication in my introduction of linear algebra course.
Now I was supprised to learn that the multiplication of matrices was not commutative. It made me think that perhaps commutativity was not a fundemental aspect of multiplication.
So having learned in my foundations of computer science course (which gave me a quicky intro to discrete mathmatics) that the foundations of mathamatics are in set theory, I went and looked up how multiplication was defined in set theory, which led me to reading about the cartesian product (which might have been covered in my foundations of comp sci course, but if it was I missed it or forgot it). The cartesian product of two sets is of course not commutative.
So now I'm curious, are integer multiplication, real number multiplication, matrix multiplication and such defined in terms of the cartesian product? If so how does that work?
Now I was supprised to learn that the multiplication of matrices was not commutative. It made me think that perhaps commutativity was not a fundemental aspect of multiplication.
So having learned in my foundations of computer science course (which gave me a quicky intro to discrete mathmatics) that the foundations of mathamatics are in set theory, I went and looked up how multiplication was defined in set theory, which led me to reading about the cartesian product (which might have been covered in my foundations of comp sci course, but if it was I missed it or forgot it). The cartesian product of two sets is of course not commutative.
So now I'm curious, are integer multiplication, real number multiplication, matrix multiplication and such defined in terms of the cartesian product? If so how does that work?
~= scwizard =~
Re: How does the cartesian product relate to other products?
If a set A has n elements, and a set be m elements, then the cartesian product AxB has n*m elements. That's pretty much it.
I NEVER use allcaps.
Re: How does the cartesian product relate to other products?
With regards to multiplication and commutativity, you might be interested in reading about Rings and Fields:
http://en.wikipedia.org/wiki/Ring_(mathematics)
http://en.wikipedia.org/wiki/Field_(mathematics)
http://en.wikipedia.org/wiki/Ring_(mathematics)
http://en.wikipedia.org/wiki/Field_(mathematics)

 Posts: 1459
 Joined: Fri Apr 20, 2007 3:27 pm UTC
 Location: The Tower of Flints. (Also known as: England.)
Re: How does the cartesian product relate to other products?
scwizard wrote:are integer multiplication, real number multiplication, matrix multiplication and such defined in terms of the cartesian product?
Yes, in a sense. Take the set of integers Z, for example. Addition is defined as a particular function f:ZxZ>Z, so that a+b := f(a, b).
But a function is defined as a set. If g:A>B, then [imath]g \subset A \times B[/imath] with the property that [imath]\forall a \in A : \exists !b \in B : (a,b) \in g[/imath]. Then we use g(a) = b as shorthand for [imath](a, b) \in g[/imath].
So in this sense, addition is a particular subset of ZxZxZ. But the properties of addition (associativity etc.) follow entirely from the choice of subset, rather than from the properties of the Cartesian product. And the subset we choose is the one which has the properties which we want for addition.
Generally I try to make myself do things I instinctively avoid, in case they are awesome.
dubsola
dubsola
Re: How does the cartesian product relate to other products?
There actually is a sense in which the Cartesian product of two sets is commutative: the set of ordered pairs (A, B) has a natural bijection to the set of ordered pairs (B, A) obtained just by switching the first and the second entry.
Anyway, as far as real number multiplication goes you can think about it this way: if you have two intervals [0, a] and [0, b] with lengths a and b, their Cartesian product is the rectangle [0, a] x [0, b] which has area ab. To make this sufficiently precise requires a tool called measure theory, but I think this is a very natural way to think about real multiplication in the sense that it's the way that multiplication was done historically (i.e. by the Egyptians and Greeks).
Matrix multiplication is very different. The fundamental idea behind it is just a composition of functions: multiplication of matrices is the same thing as composing the corresponding linear transformations. This tells you immediately that matrix multiplication is associative, but there's no reason to expect composition of functions to be commutative (for example, rotations and reflections don't commute). There's also no obvious way for Cartesian products to creep in. There's a sense in which the analogue of the Cartesian product for matrices isn't matrix multiplication, but rather the tensor product, but I'm not confident about this statement and don't really have the background to explain what I mean in detail.
As far as the more philosophical question behind your actual question: usually the reason we call something a "product" is because it obeys some kind of distributivity law with respect to some other operation we call a "sum." The sum can be a lot of things: in the case of the Cartesian product, for example, the sum is disjoint union, whereas for the integers and reals the sum is ordinary addition. In a general ring it can be any operation that obeys the right axioms. As far as matrices, for vector spaces, taking the tensor product as the product gives the direct sum as the sum, but this might be going a little too far.
Anyway, as far as real number multiplication goes you can think about it this way: if you have two intervals [0, a] and [0, b] with lengths a and b, their Cartesian product is the rectangle [0, a] x [0, b] which has area ab. To make this sufficiently precise requires a tool called measure theory, but I think this is a very natural way to think about real multiplication in the sense that it's the way that multiplication was done historically (i.e. by the Egyptians and Greeks).
Matrix multiplication is very different. The fundamental idea behind it is just a composition of functions: multiplication of matrices is the same thing as composing the corresponding linear transformations. This tells you immediately that matrix multiplication is associative, but there's no reason to expect composition of functions to be commutative (for example, rotations and reflections don't commute). There's also no obvious way for Cartesian products to creep in. There's a sense in which the analogue of the Cartesian product for matrices isn't matrix multiplication, but rather the tensor product, but I'm not confident about this statement and don't really have the background to explain what I mean in detail.
As far as the more philosophical question behind your actual question: usually the reason we call something a "product" is because it obeys some kind of distributivity law with respect to some other operation we call a "sum." The sum can be a lot of things: in the case of the Cartesian product, for example, the sum is disjoint union, whereas for the integers and reals the sum is ordinary addition. In a general ring it can be any operation that obeys the right axioms. As far as matrices, for vector spaces, taking the tensor product as the product gives the direct sum as the sum, but this might be going a little too far.
 Cleverbeans
 Posts: 1378
 Joined: Wed Mar 26, 2008 1:16 pm UTC
Re: How does the cartesian product relate to other products?
scwizard wrote:Now I was supprised to learn that the multiplication of matrices was not commutative. It made me think that perhaps commutativity was not a fundemental aspect of multiplication
I had a very similar experience when I learned about cross products. Ultimately most of my questions were answered when I started investigating Abstract Algebra  particularly groups although rings and fields helped me to form a bigger picture. Now, I think about multiplication as a special kind of binary operation that acts on certain sets in the way we're familiar with. What really got my interest peaked was when they presented two completely different sets, with two operations that *seemed* distinct in their mechanics yet behaved exactly the same way (an isomorphism). Personally I'd recommend you read up a bit on groups and you'll start to see that the questions you're asking lead to a very rich and interesting part of modern mathematics.
"Labor is prior to, and independent of, capital. Capital is only the fruit of labor, and could never have existed if labor had not first existed. Labor is the superior of capital, and deserves much the higher consideration."  Abraham Lincoln
Re: How does the cartesian product relate to other products?
Hmm, this sounds very interesting.
Now the other question I have, which I thought the OP implied, but it turns out it didn't really, is how are matrices defined in terms of sets?
Now the other question I have, which I thought the OP implied, but it turns out it didn't really, is how are matrices defined in terms of sets?
~= scwizard =~
Re: How does the cartesian product relate to other products?
An ordered pair is [imath](a,b)=\{a, \{a,b\}\}[/imath]
The cartesian product of two sets [imath]S\times T[/imath] is the set of ordered pairs [imath]\{ (s,t) \mid s\in S, t\in T\}[/imath].
A function [imath]f:S \rightarrow T[/imath] is a subset of [imath]S\times T[/imath] such that if [imath](x,y)\in f[/imath] and [imath](x,y')\in f[/imath], then [imath]y=y'[/imath]. The set of all functions from [imath]S[/imath] to [imath]T[/imath] is denoted [imath]T^S[/imath]
A natural number is an element of the set [imath]\mathbb{N}=\{n \mid\text{$n$ is in any inductive set}\}[/imath], where an inductive set is an set [imath]S[/imath] such that [imath]\{\} \in S[/imath] and if [imath]s\in S[/imath] then [imath]s \cup \{s\} \in S[/imath].
I'll leave the definitions of multiplication, addition, and so forth to the reader.
An integer is an element of the set [imath]\mathbb{Z} = \{[(a,b)]_\mathbb{Z} \mid (a,b)\in \mathbb{N}\times\mathbb{N}\}[/imath], where [imath][(a,b)]_\mathbb{Z} = \{ (c,d) \in \mathbb{N}\times\mathbb{N} \mid \exists k \in \mathbb{N} \text{ s.t. } c=a+k, d=b+k \}[/imath]. (Here, [imath][(a,b)]_\mathbb{Z}[/imath] is supposed to represent [imath]ab[/imath].)
An rational number is an element of the set [imath]\mathbb{Q} = \{[(a,b)]_\mathbb{Q} \mid (a,b)\in \mathbb{Z}\times(\mathbb{Z}\setminus \{0\})\}[/imath], where [imath][(a,b)]_\mathbb{Q} = \{ (c,d) \in \mathbb{Z}\times(\mathbb{Z}\setminus \{0\} \mid \exists k \in \mathbb{Z}\setminus \{0\} \text{ s.t. } c=a\cdot k, d=b\cdot k \}[/imath]. (Here, [imath][(a,b)]_\mathbb{Q}[/imath] is supposed to represent [imath]a/b[/imath].)
(These were wrong, see below.)
A real number is an element of the set [imath]\mathbb{R} = \{[s]_\mathbb{R} \mid s\in \mathbb{Q}^\mathbb{N}, \text{ $s$ is Cauchy}\}[/imath]. Here we say [imath]s \in \mathbb{Q}^\mathbb{N}[/imath] is Cauchy if for all [imath]\epsilon \in \mathbb{Q}[/imath] s.t. [imath]\epsilon > 0[/imath] there is some [imath]N\in\mathbb{N}[/imath] such that if [imath]n,m \in \mathbb{N}[/imath] and [imath]n>N,m>N[/imath] then [imath]\epsilon < s(n)s(m) < \epsilon[/imath]. We define [imath][s]_\mathbb{R} = \{t \in \mathbb{Q}^\mathbb{N} \mid \text{$s*t$ is Cauchy}\}[/imath], where [imath](s*t)(2n)=s(n)[/imath] and [imath](s*t)(2n+1)=t(n)[/imath].
Finally, an n by n matrix with real coefficients is a function [imath]f:n \times n \rightarrow \mathbb{R}[/imath].
Edit: fixed up the definition of real number a bit, too.
The cartesian product of two sets [imath]S\times T[/imath] is the set of ordered pairs [imath]\{ (s,t) \mid s\in S, t\in T\}[/imath].
A function [imath]f:S \rightarrow T[/imath] is a subset of [imath]S\times T[/imath] such that if [imath](x,y)\in f[/imath] and [imath](x,y')\in f[/imath], then [imath]y=y'[/imath]. The set of all functions from [imath]S[/imath] to [imath]T[/imath] is denoted [imath]T^S[/imath]
A natural number is an element of the set [imath]\mathbb{N}=\{n \mid\text{$n$ is in any inductive set}\}[/imath], where an inductive set is an set [imath]S[/imath] such that [imath]\{\} \in S[/imath] and if [imath]s\in S[/imath] then [imath]s \cup \{s\} \in S[/imath].
I'll leave the definitions of multiplication, addition, and so forth to the reader.
(These were wrong, see below.)
A real number is an element of the set [imath]\mathbb{R} = \{[s]_\mathbb{R} \mid s\in \mathbb{Q}^\mathbb{N}, \text{ $s$ is Cauchy}\}[/imath]. Here we say [imath]s \in \mathbb{Q}^\mathbb{N}[/imath] is Cauchy if for all [imath]\epsilon \in \mathbb{Q}[/imath] s.t. [imath]\epsilon > 0[/imath] there is some [imath]N\in\mathbb{N}[/imath] such that if [imath]n,m \in \mathbb{N}[/imath] and [imath]n>N,m>N[/imath] then [imath]\epsilon < s(n)s(m) < \epsilon[/imath]. We define [imath][s]_\mathbb{R} = \{t \in \mathbb{Q}^\mathbb{N} \mid \text{$s*t$ is Cauchy}\}[/imath], where [imath](s*t)(2n)=s(n)[/imath] and [imath](s*t)(2n+1)=t(n)[/imath].
Finally, an n by n matrix with real coefficients is a function [imath]f:n \times n \rightarrow \mathbb{R}[/imath].
Edit: fixed up the definition of real number a bit, too.
Last edited by antonfire on Fri Feb 06, 2009 2:06 am UTC, edited 3 times in total.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?
Re: How does the cartesian product relate to other products?
Probably not in a way you'll find very enlightening. Recall that from sets, we define the naturals, from naturals the integers, from integers the rationals, from rationals the reals. What is a matrix but an array of numbers? So the set theoretic way to define an n by n matrix is as a function from {1,2,...,n}x{1,2,...,n} to the reals (or the rationals, or complex numbers, or whatever ring you're working in). From there you define componentwise what it means to add matrices, multiply them, etc.
Re: How does the cartesian product relate to other products?
antonfire wrote:An ordered pair is [imath](a,b)=\{a, \{a,b\}\}[/imath]
The cartesian product of two sets [imath]S\times T[/imath] is the set of ordered pairs [imath]\{ (s,t) \mid s\in S, t\in T\}[/imath].
A function [imath]f:S \rightarrow T[/imath] is a subset of [imath]S\times T[/imath] such that if [imath](x,y)\in f[/imath] and [imath](x,y')\in f[/imath], then [imath]y=y'[/imath]. The set of all functions from [imath]S[/imath] to [imath]T[/imath] is denoted [imath]T^S[/imath]
A natural number is an element of the set [imath]\mathbb{N}=\{n \mid\text{$n$ is in any inductive set}\}[/imath], where an inductive set is an set [imath]S[/imath] such that [imath]\{\} \in S[/imath] and if [imath]s\in S[/imath] then [imath]s \cup \{s\} \in S[/imath].
I'll leave the definitions of multiplication, addition, and so forth to the reader.
An integer is an element of the set [imath]\mathbb{Z} = \{[(a,b)]_\mathbb{Z} \mid (a,b)\in \mathbb{N}\times\mathbb{N}\}[/imath], where [imath][(a,b)]_\mathbb{Z} = \{ (c,d) \in \mathbb{N}\times\mathbb{N} \mid \exists k \in \mathbb{N} \text{ s.t. } c=a+k, d=b+k \}[/imath]. (Here, [imath][(a,b)]_\mathbb{Z}[/imath] is supposed to represent [imath]ab[/imath].)
An rational number is an element of the set [imath]\mathbb{Q} = \{[(a,b)]_\mathbb{Q} \mid (a,b)\in \mathbb{Z}\times(\mathbb{Z}\setminus \{0\})\}[/imath], where [imath][(a,b)]_\mathbb{Q} = \{ (c,d) \in \mathbb{Z}\times(\mathbb{Z}\setminus \{0\} \mid \exists k \in \mathbb{Z}\setminus \{0\} \text{ s.t. } c=a\cdot k, d=b\cdot k \}[/imath]. (Here, [imath][(a,b)]_\mathbb{Q}[/imath] is supposed to represent [imath]a/b[/imath].)
A real number is an element of the set [imath]\mathbb{Q} = \{[s]_\mathbb{R} \mid s\in \mathbb{Q}^\mathbb{N}, \text{ $s$ is Cauchy}\}[/imath]. Here we say [imath]s \in \mathbb{Q}^\mathbb{N}[/imath] is Cauchy if for all [imath]\epsilon \in \mathbb{Q}[/imath] there is some [imath]N\in\mathbb{N}[/imath] such that if [imath]n,m \in \mathbb{N}[/imath] and [imath]n>N,m>N[/imath] then [imath]\epsilon < s(n)s(m) < \epsilon[/imath]. We define [imath][s]_\mathbb{R} = \{t \in \mathbb{Q}^\mathbb{N} \mid \text{$s*t$ is Cauchy}\}[/imath], where [imath](s*t)(2n)=s(n)[/imath] and [imath](s*t)(2n+1)=t(n)[/imath].
Finally, an n by n matrix with real coefficients is a function [imath]f:n \times n \rightarrow \mathbb{R}[/imath].
Thanks. I'll study the resources I have and see what kind of sense I can make of this, but from an initial glance it seems very interesting, especially the part about how functions are defined.
~= scwizard =~
Re: How does the cartesian product relate to other products?
Whoops, I misdefined [imath]\mathbb{Z}[/imath] and [imath]\mathbb{Q}[/imath].
An integer is an element of the set [imath]\mathbb{Z} = \{[(a,b)]_\mathbb{Z} \mid (a,b)\in \mathbb{N}\times\mathbb{N}\}[/imath], where [imath][(a,b)]_\mathbb{Z} = \{ (c,d) \in \mathbb{N}\times\mathbb{N} \mid \exists k,l \in \mathbb{N} \text{ s.t. } c+l=a+k, d+l=b+k \}[/imath]. (Here, [imath][(a,b)]_\mathbb{Z}[/imath] is supposed to represent [imath]ab[/imath].)
An rational number is an element of the set [imath]\mathbb{Q} = \{[(a,b)]_\mathbb{Q} \mid (a,b)\in \mathbb{Z}\times(\mathbb{Z}\setminus \{0\})\}[/imath], where [imath][(a,b)]_\mathbb{Q} = \{ (c,d) \in \mathbb{Z}\times(\mathbb{Z}\setminus \{0\} \mid \exists k,l \in \mathbb{Z}\setminus \{0\} \text{ s.t. } c\cdot l=a\cdot k, d\cdot l=b\cdot k \}[/imath]. (Here, [imath][(a,b)]_\mathbb{Q}[/imath] is supposed to represent [imath]a/b[/imath].)
An integer is an element of the set [imath]\mathbb{Z} = \{[(a,b)]_\mathbb{Z} \mid (a,b)\in \mathbb{N}\times\mathbb{N}\}[/imath], where [imath][(a,b)]_\mathbb{Z} = \{ (c,d) \in \mathbb{N}\times\mathbb{N} \mid \exists k,l \in \mathbb{N} \text{ s.t. } c+l=a+k, d+l=b+k \}[/imath]. (Here, [imath][(a,b)]_\mathbb{Z}[/imath] is supposed to represent [imath]ab[/imath].)
An rational number is an element of the set [imath]\mathbb{Q} = \{[(a,b)]_\mathbb{Q} \mid (a,b)\in \mathbb{Z}\times(\mathbb{Z}\setminus \{0\})\}[/imath], where [imath][(a,b)]_\mathbb{Q} = \{ (c,d) \in \mathbb{Z}\times(\mathbb{Z}\setminus \{0\} \mid \exists k,l \in \mathbb{Z}\setminus \{0\} \text{ s.t. } c\cdot l=a\cdot k, d\cdot l=b\cdot k \}[/imath]. (Here, [imath][(a,b)]_\mathbb{Q}[/imath] is supposed to represent [imath]a/b[/imath].)
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?
Re: How does the cartesian product relate to other products?
That's a horrible way to define a matrix. Among many other things, it gives absolutely no motivation as to how to define matrix multiplication.
The standard treatment is as follows: once we've defined a finitedimensional vector space over [imath]\mathbb{R}[/imath], we define a linear transformation between two vector spaces [imath]L : V_1 \to V_2[/imath] as a function satisfying the following two properties:
 Linearity: [imath]L(v_1+ v_2) = L(v_1) + L(v_2)[/imath]
 Scalar multiplication: [imath]L(cv_1) = cL(v_1)[/imath].
Because every finitedimensional vector space has a finite basis, the set of all linear transformations between two vector spaces [imath]V_1, V_2[/imath] of dimensions [imath]n, m[/imath] can be described by a total of [imath]mn[/imath] numbers describing what each basis vector in [imath]V_1[/imath] is mapped to as a linear combination of basis vectors of [imath]V_2[/imath].
Multiplication of matrices is given by composition of linear transformations, hence it is possible to compose two linear transformations if and only if the range of one is the domain of the other, i.e. there are three vector spaces [imath]V_1, V_2, V_3[/imath] such that [imath]L_1 : V_1 \to V_2[/imath] and [imath]L_2 : V_2 \to V_3[/imath]. This is the same as the usual condition for multiplying by matrices. This is in particular always possible if the vector spaces are identical.
The standard treatment is as follows: once we've defined a finitedimensional vector space over [imath]\mathbb{R}[/imath], we define a linear transformation between two vector spaces [imath]L : V_1 \to V_2[/imath] as a function satisfying the following two properties:
 Linearity: [imath]L(v_1+ v_2) = L(v_1) + L(v_2)[/imath]
 Scalar multiplication: [imath]L(cv_1) = cL(v_1)[/imath].
Because every finitedimensional vector space has a finite basis, the set of all linear transformations between two vector spaces [imath]V_1, V_2[/imath] of dimensions [imath]n, m[/imath] can be described by a total of [imath]mn[/imath] numbers describing what each basis vector in [imath]V_1[/imath] is mapped to as a linear combination of basis vectors of [imath]V_2[/imath].
Multiplication of matrices is given by composition of linear transformations, hence it is possible to compose two linear transformations if and only if the range of one is the domain of the other, i.e. there are three vector spaces [imath]V_1, V_2, V_3[/imath] such that [imath]L_1 : V_1 \to V_2[/imath] and [imath]L_2 : V_2 \to V_3[/imath]. This is the same as the usual condition for multiplying by matrices. This is in particular always possible if the vector spaces are identical.
Last edited by t0rajir0u on Fri Feb 06, 2009 7:47 pm UTC, edited 1 time in total.
Re: How does the cartesian product relate to other products?
Yeah, my post was mostly meant to be a snarky way of saying "you don't want to know", but if people want to work out how the real numbers and everything are built up from set theory, by all means, go ahead.
t0rajir0u is absolutely right, the right way to think about matrices is in terms of linear transformation. (Though a matrix is not itself a linear transformation, just a way of writing one down with respect to a particular basis or two.) See also: this thread.
Building that up from set theory takes even more work, though, so I took a shortcut.
t0rajir0u is absolutely right, the right way to think about matrices is in terms of linear transformation. (Though a matrix is not itself a linear transformation, just a way of writing one down with respect to a particular basis or two.) See also: this thread.
Building that up from set theory takes even more work, though, so I took a shortcut.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: How does the cartesian product relate to other products?
So you can use n x m = n * m to define multiplication of natural numbers (ie, the counting numbers  0, 1, 2, 3, etc).
Ie, first you define succ(n) = { {n} } U n, with 0 = {}. Then n = n. (succ is the successor, or increment, function).
Then define a+b = a if b is 0, or succ(a + x) where succ(x) = b.
Next, define "a * b" to be the number c such that c = a x b.
(where x is the Cartesian product)
...
Now something is called a multiplication in basically two different cases. First, it is used as a generic group operation when you don't know if the group commutes.
But it is more strongly used when you have a group operation that distributes over another group operation  ie, you have a group operation + on some set, and you have another group operation * on the same set such that a*(b+c) = a*b + a*c.
This holds for matrix composition and addition  hence calling it matrix multiplication. Because in a natural sense, it is multiplication.
...
How do you get back to the Cartesian product? Well, I defined multiplication on the natural (counting) numbers based on the Cartesian product.
From that, you can define an integer Z = {0,1} x N, where the first element of the pair is the sign of the integer. (Doesn't really matter which you pick as + and which as ).
For two integers a b, a*b = ( (a_0 == b_0)?0:1 , a_1 * b_1 ). Addition is defined somewhat similarly.
From that you can build the rationals. Rational multiplication/addition is defined in terms of integer multiplication.
Then you define R using cuts or cauchy sequences or particular functions on Q, and define multiplication on R in terms of multiplication on Q.
All of which ... ends up falling down to the definition of the Cartesian product.
Naturally you can do all of this differently, and get a similar result.
(Apologies if I screwed up any of the above constructions.)
Ie, first you define succ(n) = { {n} } U n, with 0 = {}. Then n = n. (succ is the successor, or increment, function).
Then define a+b = a if b is 0, or succ(a + x) where succ(x) = b.
Next, define "a * b" to be the number c such that c = a x b.
(where x is the Cartesian product)
...
Now something is called a multiplication in basically two different cases. First, it is used as a generic group operation when you don't know if the group commutes.
But it is more strongly used when you have a group operation that distributes over another group operation  ie, you have a group operation + on some set, and you have another group operation * on the same set such that a*(b+c) = a*b + a*c.
This holds for matrix composition and addition  hence calling it matrix multiplication. Because in a natural sense, it is multiplication.
...
How do you get back to the Cartesian product? Well, I defined multiplication on the natural (counting) numbers based on the Cartesian product.
From that, you can define an integer Z = {0,1} x N, where the first element of the pair is the sign of the integer. (Doesn't really matter which you pick as + and which as ).
For two integers a b, a*b = ( (a_0 == b_0)?0:1 , a_1 * b_1 ). Addition is defined somewhat similarly.
From that you can build the rationals. Rational multiplication/addition is defined in terms of integer multiplication.
Then you define R using cuts or cauchy sequences or particular functions on Q, and define multiplication on R in terms of multiplication on Q.
All of which ... ends up falling down to the definition of the Cartesian product.
Naturally you can do all of this differently, and get a similar result.
(Apologies if I screwed up any of the above constructions.)
Last edited by Yakk on Fri Feb 06, 2009 2:55 am UTC, edited 1 time in total.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
 NathanielJ
 Posts: 882
 Joined: Sun Jan 13, 2008 9:04 pm UTC
Re: How does the cartesian product relate to other products?
t0rajir0u wrote:That's a horrible way to define a matrix.
It's a fine way to define a matrix, depending on your context. In particular, if you want to deal with higherdimensional matrices, then that's a very good definition to use, since you can just slap on d cartesian products, where d is the dimension you want (and a 2dimensional matrix is what we normally refer to as a matrix).
I just read a paper actually about generalizing doubly stochastic matrices in exactly that way.
Re: How does the cartesian product relate to other products?
Yakk wrote:Now something is called a multiplication in basically two different cases. First, it is used as a generic group operation when you don't know if the group commutes.
But it is more strongly used when you have a group operation that distributes over another group operation  ie, you have a group operation + on some set, and you have another group operation * on the same set such that a*(b+c) = a*b + a*c.
This holds for matrix composition and addition  hence calling it matrix multiplication. Because in a natural sense, it is multiplication.
Aren't there other operations on matrices that fulfill those requirements though? Why not call them multiplication instead?
~= scwizard =~
 NathanielJ
 Posts: 882
 Joined: Sun Jan 13, 2008 9:04 pm UTC
Re: How does the cartesian product relate to other products?
scwizard wrote:Yakk wrote:Now something is called a multiplication in basically two different cases. First, it is used as a generic group operation when you don't know if the group commutes.
But it is more strongly used when you have a group operation that distributes over another group operation  ie, you have a group operation + on some set, and you have another group operation * on the same set such that a*(b+c) = a*b + a*c.
This holds for matrix composition and addition  hence calling it matrix multiplication. Because in a natural sense, it is multiplication.
Aren't there other operations on matrices that fulfill those requirements though? Why not call them multiplication instead?
Yep, the Hadamard Product is probably the most wellknown "other" matrix multiplication. People use the term "multiplication" for the Hadamard product (and other products) as well, but you just have to specify which product/multiplication you're using. And since the "standard" matrix multiplication that you know and love is by far the most common and useful, it's what is almost always meant when someone says "matrix multiplication" without any further qualification.
Re: How does the cartesian product relate to other products?
Interesting.
I thought that multiplication might follow directly from the cartesian product for other things, because that's the case for natural numbers (in a way sort of), but apparently multiplication is just a name for a function with a series of properties.
I thought that multiplication might follow directly from the cartesian product for other things, because that's the case for natural numbers (in a way sort of), but apparently multiplication is just a name for a function with a series of properties.
~= scwizard =~
 parallax
 Posts: 157
 Joined: Wed Jan 31, 2007 5:06 pm UTC
 Location: The Emergency Intelligence Incinerator
Re: How does the cartesian product relate to other products?
NathanielJ wrote:t0rajir0u wrote:That's a horrible way to define a matrix.
It's a fine way to define a matrix, depending on your context. In particular, if you want to deal with higherdimensional matrices, then that's a very good definition to use, since you can just slap on d cartesian products, where d is the dimension you want (and a 2dimensional matrix is what we normally refer to as a matrix).
I just read a paper actually about generalizing doubly stochastic matrices in exactly that way.
Higher dimensional matrices (tensors) are usually defined as linear functions that map m vectors to n vectors. T: V^{m} > V^{n}
Cake and grief counseling will be available at the conclusion of the test.
 NathanielJ
 Posts: 882
 Joined: Sun Jan 13, 2008 9:04 pm UTC
Re: How does the cartesian product relate to other products?
parallax wrote:NathanielJ wrote:t0rajir0u wrote:That's a horrible way to define a matrix.
It's a fine way to define a matrix, depending on your context. In particular, if you want to deal with higherdimensional matrices, then that's a very good definition to use, since you can just slap on d cartesian products, where d is the dimension you want (and a 2dimensional matrix is what we normally refer to as a matrix).
I just read a paper actually about generalizing doubly stochastic matrices in exactly that way.
Higher dimensional matrices (tensors) are usually defined as linear functions that map m vectors to n vectors. T: V^{m} > V^{n}
Yes, they are usually defined that way if you are interested in their properties as linear operators. The entire field of matrix analysis doesn't really care so much about that though, and in my experience the other definition is much more common in that branch.
I'm in no way saying that the definition given earlier is the standard or only one, I'm just saying there nothing "wrong" with it and in fact many people use it.
Re: How does the cartesian product relate to other products?
antonfire wrote:Finally, an n by n matrix with real coefficients is a function [imath]f:n \times n \rightarrow \mathbb{R}[/imath].
I don't get this. A matrix is a function with a codomain consisting of a single real number?
That doesn't make any sense. That would mean that you could evaluate a matrix to a single real number.
~= scwizard =~
 parallax
 Posts: 157
 Joined: Wed Jan 31, 2007 5:06 pm UTC
 Location: The Emergency Intelligence Incinerator
Re: How does the cartesian product relate to other products?
The identity matrix in three dimensions can be defined either as I: m:{1,2,3}x n:{1,2,3} > r:R where r=1 if m=n and r=0 if m=/=n or as the function I: x:R^{3} > y:R^{3} where y=x. Both are valid and useful depending on what aspect of matrices you're studying.
Cake and grief counseling will be available at the conclusion of the test.
Re: How does the cartesian product relate to other products?
I still don't get it, a matrix is a set of functions?
~= scwizard =~
Re: How does the cartesian product relate to other products?
They're just defining a matrix as a function which takes some ordered pair of integers (i,j) and spits out some real number (the i,j entry of the matrix). It's the purely settheoretical definition of the object.
Re: How does the cartesian product relate to other products?
No, a matrix is a function with codomain [imath]\mathbb{R}[/imath], the set of real numbers.scwizard wrote:I don't get this. A matrix is a function with a codomain consisting of a single real number?
No, you could, given a matrix and two natural numbers between 0 and n1 (the column number and the row number), get an associated real number (the entry of the matrix at that column and row).scwizard wrote:That doesn't make any sense. That would mean that you could evaluate a matrix to a single real number.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?
 qinwamascot
 Posts: 688
 Joined: Sat Oct 04, 2008 8:50 am UTC
 Location: Oklahoma, U.S.A.
Re: How does the cartesian product relate to other products?
There's a graphical representation of the similarities between different types of products, but it doesn't really continue to work once we get to things like inner products and cross products. It's just off the top of my head; there might be a better one.
Imagine you have 2 countable sets. Position the elements of 1 of the sets as columns and the other as intersecting rows. The resulting table is the cartesian product. For scalar multiplication, imagine line segments of length a and b intersecting at a right angle. The area of the resulting rectangle is the product of the lengths. It's possible to construct a 3D representation of a matrix product this way I think, although it requires summation over one dimension. In a very basic sense, the product of 2 things involves taking those objects, rotating one by 90 degrees, and observing the resultant object formed by the rectangular grid. This also works for the dot product of vectors, as v_{1}^{T}v_{2} is another way of representing this.
It's clearly not a rigorous definition (i.e. what does it mean to rotate an arbitrary object by 90 degrees?) but it does give some insight into what a product might mean in a general sense.
Imagine you have 2 countable sets. Position the elements of 1 of the sets as columns and the other as intersecting rows. The resulting table is the cartesian product. For scalar multiplication, imagine line segments of length a and b intersecting at a right angle. The area of the resulting rectangle is the product of the lengths. It's possible to construct a 3D representation of a matrix product this way I think, although it requires summation over one dimension. In a very basic sense, the product of 2 things involves taking those objects, rotating one by 90 degrees, and observing the resultant object formed by the rectangular grid. This also works for the dot product of vectors, as v_{1}^{T}v_{2} is another way of representing this.
It's clearly not a rigorous definition (i.e. what does it mean to rotate an arbitrary object by 90 degrees?) but it does give some insight into what a product might mean in a general sense.
Quiznos>Subway
 Incompetent
 Posts: 396
 Joined: Mon May 26, 2008 12:08 pm UTC
 Location: Brussels
Re: How does the cartesian product relate to other products?
itaibn wrote:If a set A has n elements, and a set be m elements, then the cartesian product AxB has n*m elements. That's pretty much it.
Things get more interesting if you try to define the Cartesian product of infinitely many sets. Here is one way of stating the Axiom of Choice:
"The Cartesian product of nonempty sets is nonempty."
Re: How does the cartesian product relate to other products?
antonfire wrote:No, you could, given a matrix and two natural numbers between 0 and n1 (the column number and the row number), get an associated real number (the entry of the matrix at that column and row).scwizard wrote:That doesn't make any sense. That would mean that you could evaluate a matrix to a single real number.
Oh I see now. That's interesting and makes complete sense. But ya, the question I asked was already answered, me wondering about how matrices are defined in terms of functions is just curiosity.
~= scwizard =~
 parallax
 Posts: 157
 Joined: Wed Jan 31, 2007 5:06 pm UTC
 Location: The Emergency Intelligence Incinerator
Re: How does the cartesian product relate to other products?
In Nathaniel's definition of a matrix, a 3x3 matrix is just a list of 9 real numbers, so it can be defined as a function with takes as input one of the nine positions of the matrix and takes as output whichever element of the matrix is in that position.
Linear algebra takes advantage of the fact that when you multiply a matrix times a vector, you get another vector. So, in that sense, a matrix is a function that takes a vector and gives you another vector.
Linear algebra takes advantage of the fact that when you multiply a matrix times a vector, you get another vector. So, in that sense, a matrix is a function that takes a vector and gives you another vector.
Cake and grief counseling will be available at the conclusion of the test.
Re: How does the cartesian product relate to other products?
NathanielJ wrote:if you want to deal with higherdimensional matrices, then that's a very good definition to use, since you can just slap on d cartesian products
That's a horrible way to define a tensor, too, and for exactly the same reason. Multilinear algebra, like linear algebra, is generally best done from a coordinatefree perspective.
The only natural reason I can think of to define a matrix in that way is graphtheoretic (which is very naturally a function on [imath]V \times V[/imath], the set of pairs of vertices), where matrix composition becomes about counting paths. The tensor generalization, I suppose, is about hypergraphs. This works, but my point is that without additional categorical structure there isn't a natural way to understand what it is that matrices actually do.
If you want another reason: it's not at all obvious how to generalize the component definition of a matrix to, say, a linear transformation on a Hilbert space with uncountable dimension, whereas the abstract definition carries over readily (once you add continuity to the mix).
 NathanielJ
 Posts: 882
 Joined: Sun Jan 13, 2008 9:04 pm UTC
Re: How does the cartesian product relate to other products?
t0rajir0u wrote:NathanielJ wrote:if you want to deal with higherdimensional matrices, then that's a very good definition to use, since you can just slap on d cartesian products
That's a horrible way to define a tensor, too, and for exactly the same reason. Multilinear algebra, like linear algebra, is generally best done from a coordinatefree perspective.
The only natural reason I can think of to define a matrix in that way is graphtheoretic (which is very naturally a function on [imath]V \times V[/imath], the set of pairs of vertices), where matrix composition becomes about counting paths. The tensor generalization, I suppose, is about hypergraphs. This works, but my point is that without additional categorical structure there isn't a natural way to understand what it is that matrices actually do.
If you want another reason: it's not at all obvious how to generalize the component definition of a matrix to, say, a linear transformation on a Hilbert space with uncountable dimension, whereas the abstract definition carries over readily (once you add continuity to the mix).
Again, you're just looking at a matrix from a completely different perspective. Just because the coordinate function definition makes no sense when a matrix is thought of as a linear operator does *not* mean it makes no sense when it's thought about just as a matrix. There are *many* interesting properties of matrices that have absolutely nothing to do with linear operators, and that's exactly what matrix analysis deals with. Looking at what you can determine about a matrix from its sign pattern (a field that's reasonably active right now) is a good example of a matrix question that has *nothing* to do with linear operators and indeed *has* to be defined coordinatewise (because it's not invariant under basis change, for example).
Also, not all contexts care about what matrices do. Sometimes the geometric structure of the set of matrices (or a subset of matrices) is what's of interest, and the given definition is a fine and dandy one in that context as well.
Who is online
Users browsing this forum: No registered users and 14 guests