How does the cartesian product relate to other products?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

How does the cartesian product relate to other products?

Postby scwizard » Thu Feb 05, 2009 8:36 pm UTC

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?
~= scwizard =~

itaibn
Posts: 142
Joined: Mon Dec 29, 2008 7:06 pm UTC

Re: How does the cartesian product relate to other products?

Postby itaibn » Thu Feb 05, 2009 8:42 pm UTC

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 all-caps.

Tiax
Posts: 53
Joined: Wed Aug 29, 2007 3:22 pm UTC

Re: How does the cartesian product relate to other products?

Postby Tiax » Thu Feb 05, 2009 8:45 pm UTC

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)

Ended
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?

Postby Ended » Thu Feb 05, 2009 8:54 pm UTC

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

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: How does the cartesian product relate to other products?

Postby t0rajir0u » Thu Feb 05, 2009 9:22 pm UTC

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.

User avatar
Cleverbeans
Posts: 1378
Joined: Wed Mar 26, 2008 1:16 pm UTC

Re: How does the cartesian product relate to other products?

Postby Cleverbeans » Thu Feb 05, 2009 10:17 pm UTC

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

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: How does the cartesian product relate to other products?

Postby scwizard » Thu Feb 05, 2009 10:54 pm UTC

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?
~= scwizard =~

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: How does the cartesian product relate to other products?

Postby antonfire » Fri Feb 06, 2009 12:11 am UTC

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]a-b[/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.
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?

Buttons
Posts: 858
Joined: Wed May 02, 2007 3:27 pm UTC
Location: Somerville

Re: How does the cartesian product relate to other products?

Postby Buttons » Fri Feb 06, 2009 12:13 am UTC

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 component-wise what it means to add matrices, multiply them, etc.

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: How does the cartesian product relate to other products?

Postby scwizard » Fri Feb 06, 2009 1:34 am UTC

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]a-b[/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 =~

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: How does the cartesian product relate to other products?

Postby antonfire » Fri Feb 06, 2009 1:42 am UTC

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]a-b[/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?

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: How does the cartesian product relate to other products?

Postby t0rajir0u » Fri Feb 06, 2009 1:42 am UTC

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 finite-dimensional 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 finite-dimensional 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.

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: How does the cartesian product relate to other products?

Postby antonfire » Fri Feb 06, 2009 1:53 am UTC

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.
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?

User avatar
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?

Postby Yakk » Fri Feb 06, 2009 2:01 am UTC

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.)
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.

User avatar
NathanielJ
Posts: 882
Joined: Sun Jan 13, 2008 9:04 pm UTC

Re: How does the cartesian product relate to other products?

Postby NathanielJ » Fri Feb 06, 2009 2:30 am UTC

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 higher-dimensional 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 2-dimensional 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.
Homepage: http://www.njohnston.ca
Conway's Game of Life: http://www.conwaylife.com

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: How does the cartesian product relate to other products?

Postby scwizard » Fri Feb 06, 2009 3:15 am UTC

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 =~

User avatar
NathanielJ
Posts: 882
Joined: Sun Jan 13, 2008 9:04 pm UTC

Re: How does the cartesian product relate to other products?

Postby NathanielJ » Fri Feb 06, 2009 4:15 am UTC

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 well-known "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.
Homepage: http://www.njohnston.ca
Conway's Game of Life: http://www.conwaylife.com

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: How does the cartesian product relate to other products?

Postby scwizard » Fri Feb 06, 2009 5:00 am UTC

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.
~= scwizard =~

User avatar
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?

Postby parallax » Fri Feb 06, 2009 5:03 am UTC

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 higher-dimensional 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 2-dimensional 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: Vm -> Vn
Cake and grief counseling will be available at the conclusion of the test.

User avatar
NathanielJ
Posts: 882
Joined: Sun Jan 13, 2008 9:04 pm UTC

Re: How does the cartesian product relate to other products?

Postby NathanielJ » Fri Feb 06, 2009 5:21 am UTC

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 higher-dimensional 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 2-dimensional 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: Vm -> Vn


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.
Homepage: http://www.njohnston.ca
Conway's Game of Life: http://www.conwaylife.com

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: How does the cartesian product relate to other products?

Postby scwizard » Fri Feb 06, 2009 5:47 am UTC

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 =~

User avatar
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?

Postby parallax » Fri Feb 06, 2009 6:02 am UTC

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:R3 -> y:R3 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.

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: How does the cartesian product relate to other products?

Postby scwizard » Fri Feb 06, 2009 6:14 am UTC

I still don't get it, a matrix is a set of functions?
~= scwizard =~

auteur52
Posts: 165
Joined: Sun Mar 23, 2008 11:08 pm UTC

Re: How does the cartesian product relate to other products?

Postby auteur52 » Fri Feb 06, 2009 6:23 am UTC

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 set-theoretical definition of the object.

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: How does the cartesian product relate to other products?

Postby antonfire » Fri Feb 06, 2009 7:22 am UTC

scwizard wrote:I don't get this. A matrix is a function with a codomain consisting of a single real number?
No, a matrix is a function with codomain [imath]\mathbb{R}[/imath], the set of real numbers.

scwizard wrote:That doesn't make any sense. That would mean that you could evaluate a matrix to a single real number.
No, you could, given a matrix and two natural numbers between 0 and n-1 (the column number and the row number), get an associated real number (the entry of the matrix at that column and row).
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?

User avatar
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?

Postby qinwamascot » Fri Feb 06, 2009 9:00 am UTC

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 3-D 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 v1Tv2 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

User avatar
Incompetent
Posts: 396
Joined: Mon May 26, 2008 12:08 pm UTC
Location: Brussels

Re: How does the cartesian product relate to other products?

Postby Incompetent » Fri Feb 06, 2009 12:15 pm UTC

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 non-empty sets is non-empty."

scwizard
Posts: 519
Joined: Sun Mar 04, 2007 6:29 pm UTC
Location: New York City
Contact:

Re: How does the cartesian product relate to other products?

Postby scwizard » Fri Feb 06, 2009 3:29 pm UTC

antonfire wrote:
scwizard wrote:That doesn't make any sense. That would mean that you could evaluate a matrix to a single real number.
No, you could, given a matrix and two natural numbers between 0 and n-1 (the column number and the row number), get an associated real number (the entry of the matrix at that column and row).

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 =~

User avatar
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?

Postby parallax » Fri Feb 06, 2009 5:43 pm UTC

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.
Cake and grief counseling will be available at the conclusion of the test.

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: How does the cartesian product relate to other products?

Postby t0rajir0u » Fri Feb 06, 2009 7:55 pm UTC

NathanielJ wrote:if you want to deal with higher-dimensional 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 coordinate-free perspective.

The only natural reason I can think of to define a matrix in that way is graph-theoretic (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).

User avatar
NathanielJ
Posts: 882
Joined: Sun Jan 13, 2008 9:04 pm UTC

Re: How does the cartesian product relate to other products?

Postby NathanielJ » Fri Feb 06, 2009 8:31 pm UTC

t0rajir0u wrote:
NathanielJ wrote:if you want to deal with higher-dimensional 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 coordinate-free perspective.

The only natural reason I can think of to define a matrix in that way is graph-theoretic (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 coordinate-wise (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.
Homepage: http://www.njohnston.ca
Conway's Game of Life: http://www.conwaylife.com


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 14 guests