Alneyan
Level: Smitemaster
Rank Points: 622
Registered: 07-06-2004
IP: Logged

I've recently taken up some math after a lengthy AWOL; I gather said math is fairly elementary (at least as far as such things go), and I'm definitely not a specialist of the subject. I'm looking for some background information and/or a more general approach about a few questions; I can already find the answers, but I'm not happy with the process I use.

* 15² = 225, 14*16=224, 13*17=221 ... and a * b = [(a + b) / 2]² - [(a - b) / 2]² . I've used a form of this formula shortly after I learned multiplications in the first place, so I only have an intuitive understanding of the thing ("it's obvious"). Is the formula actually so trivial to prove and to construct? I have not been able to find a constructive proof, either by looking it up or with pen and paper, perhaps because I've taken it for granted for so long.

* With x, y, z natural numbers, is there a closed form to resolve equations like x^2 - y^2 = z ? (with z=192, say) My current method is to use the form (x+y) (x-y) and to express z as the product of two of its factors (16 X 12, 24 X 8...). (x+y) corresponds to the higher factor, (x-y) to the lower one, and it is trivial to find the actual xs and ys. I suspect there exists a much faster way to compute all the x,y since the process is so repetitive and it looks so much like other problems.

* (1 1
1 0) is the matrix A. A^n can be expressed in terms of Fibonacci, of course. The only way I know to show this relation is through induction, but that seems unelegant and it virtually overlooks the fact that A is a matrix. So, is it possible to quickly show the relation by using a property of matrices?


Thanks for any answer, enlightenment or answer you might provide! Please let me know if my explanations are about as clear as a moonless night; I'm definitely not used to writing about math in English.

---

[Last edited by Alneyan at 03-31-2007 01:18 PM]

zex20913
Level: Smitemaster

Rank Points: 1723
Registered: 02-04-2003
IP: Logged

For the first one, I've found a proof that's not really constructive, but I've found one that works.

Assume A is the larger. Let the difference between A and B is C. So A=B+C.

AB=(B+C)(B)=B^2+BC. We want to complete the square now, so we add and subtract (C/2)^2. Now we have B^2+BC+(C/2)^2-(C/2)^2. Completing the square yields (B+(C/2))^2-(C/2)^2=((B+B+C)/2)^2-(C/2)^2.

B+C=A, and C=A-B.

We then get AB=((B+A)/2)^2-((A-B)/2)^2.

Totally non-geometric, unfortunately.

____________________________

KevG
Level: Smiter

Rank Points: 333
Registered: 08-16-2004
IP: Logged

Basic?!?

Just proving the first equation is pretty much trivial:
[(a + b) / 2]^2 - [(a - b) / 2]^2=(a/2+b/2)^2-(a/2-b/2)^2=
(a/2)^2+2(ab/4)+(b/2)^2-((a/2)^2-2(ab/4)+(b/2)^2)=
(a/2)^2+ab/2+(b/2)^2-(a/2)^2+ab/2-(b/2)^2=ab.
As far as deriving it in the first place, I suspect it's just a matter of noticing the pattern and verifying it.

krammer
Level: Smitemaster

Rank Points: 904
Registered: 02-12-2003
IP: Logged

File: proof.PNG (4.1 KB)
Downloaded 418 times.
License: Public Domain

Here's a vaguely geometric proof:

the red rectangles have area a*b. The whole thing has are (a+b)^2. The green square has area (a-b)^2.

Now notice that the yellow and blue together make another, fourth rectangle of size a*b. So we have that (a+b)^2 = (a-b)^2 + 4a*b and simple rearrangement gives the required result.

____________________________
+++ Divide by Cucumber Error +++ Please Reinstall Universe and Reboot +++

"Oook!"

---

[Last edited by krammer at 03-31-2007 02:20 PM]

Alneyan
Level: Smitemaster
Rank Points: 622
Registered: 07-06-2004
IP: Logged

KevG wrote:
As far as deriving it in the first place, I suspect it's just a matter of noticing the pattern and verifying it.

Yeah, I was kind of expecting something... grander. Thanks everyone, that should be enough for the first point.

"Basic" is code for "hey, it's only addition! How hard can it be? Next week's homework is Fermat's last theorem".

Pneh
Level: Master Delver

Rank Points: 154
Registered: 09-09-2006
IP: Logged

I don't understand anything that is going on on this topic...

____________________________

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

* With x, y, z natural numbers, is there a closed form to resolve equations like x^2 - y^2 = z ? (with z=192, say) My current method is to use the form (x+y) (x-y) and to express z as the product of two of its factors (16 X 12, 24 X 8...). (x+y) corresponds to the higher factor, (x-y) to the lower one, and it is trivial to find the actual xs and ys. I suspect there exists a much faster way to compute all the x,y since the process is so repetitive and it looks so much like other problems.

I don't know, but I suspect not. What you want to look into is diophantine (sp?) equations. I don't know a lot of the theory of them, but solving them usually involves at least some sort of iterative process, rather than closed form solutions.

* (1 1
1 0) is the matrix A. A^n can be expressed in terms of Fibonacci, of course. The only way I know to show this relation is through induction, but that seems unelegant and it virtually overlooks the fact that A is a matrix. So, is it possible to quickly show the relation by using a property of matrices?

again, I've never been very good with matrices, but it seems like the result is dependent on the nature of the elements of the matrix, so its unlikely (though not impossible) that at least part of the proof has to do with the elements themselves. There IS a closed form formula for the fibonacci sequence, so perhaps you could use that, though I suspect you'll still have to do some induction to show that A^n conforms to this formula.



____________________________
Progress Quest Progress

zex20913
Level: Smitemaster

Rank Points: 1723
Registered: 02-04-2003
IP: Logged

The third!

[a b] X [1 1]
[c d]   [1 0]

yields

[a+b a]
[c+d c]

via matrix multiplication (left to right.)

Both rows have the same recurrence relation, which is obviously the Fibonacci recursion after a couple more iterations. The only difference is the starting numbers, but they both create the "traditional" Fibonacci sequence.

____________________________

---

[Last edited by zex20913 at 03-31-2007 03:43 PM]

Alneyan
Level: Smitemaster
Rank Points: 622
Registered: 07-06-2004
IP: Logged

stigant wrote:
I don't know, but I suspect not. What you want to look into is diophantine (sp?) equations. I don't know a lot of the theory of them, but solving them usually involves at least some sort of iterative process, rather than closed form solutions.

Thanks! I've run into Diophantine equations, but it was the linear kind; back to Diophantine, but second degree then.

again, I've never been very good with matrices [...]

I don't know much about matrices myself, so I tend to be a wee bit too enthusiastic about them and I'm always hoping for a shortcut of some sort. I should ask this question in a more general way, actually.

* Given any 2X2 matrix A, is there any other way besides the naive approach to calculate A^n ? (It doesn't seem so, but linear algebra only evokes scar(r)ed sophomore students for me.)

* While matrix multiplication is trendy, I wonder why matrix multiplication is traditionally defined as "rows in A against columns in B". It seems to me that transposing B before doing the multiplication (so "rows in A against rows in B") is easier to understand.

So, is there a loophole in the "transposing matrices" business? Or am I just the odd case who cannot work the "row against column" way, preferring to stay horizontal? If nothing else, "A X B transposed" is a lot sweeter when implementing matrix multiplication in (at least) some programming languages.

---

[Last edited by Alneyan at 03-31-2007 05:30 PM]

MartianInvader
Level: Master Delver
Rank Points: 126
Registered: 01-30-2004
IP: Logged

For the second problem:



For the third problem:



Hope that helps!

____________________________
Yes, I very rarely post. But I DO keep coming back to check the forum.

---

[Last edited by MartianInvader at 03-31-2007 09:04 PM]

Jatopian
Level: Smitemaster
Rank Points: 1842
Registered: 07-31-2005
IP: Logged

I object; Matrices are not basic math! Basic math is 1+1!

____________________________
DROD has some really great music.
Make your pressure plates 3.0 style!
DROD architecture idea generator

MartianInvader
Level: Master Delver
Rank Points: 126
Registered: 01-30-2004
IP: Logged

Jatopian wrote:
I object; Matrices are not basic math! Basic math is 1+1!

1 + 1 = 0, mod 2

Many thanks to whoever modded up that last post and made me a Master Delver!

Incidentally, does anyone know how to indent things in these posts? I was using spaces which looked fine in the text-entry box, but a long row of spaces would get squashed to a single space in the final post and make my pretty formatting go all loopy!

____________________________
Yes, I very rarely post. But I DO keep coming back to check the forum.

---

[Last edited by MartianInvader at 03-31-2007 09:12 PM]

Alneyan
Level: Smitemaster
Rank Points: 622
Registered: 07-06-2004
IP: Logged

Your solution for the second problem is pretty much the same as mine, except you actually wrote it in full and more formally. I'm not done reading up on the Diophantine Equations yet, but it *sounds* like the trick.

I'm impressed by your matrices answer. Just give me a couple days to absorb it in full, though.

Why am I doing math (and even kind of enjoying it, almost) when I ought to be studying my English, I wonder.

Watcher
Level: Smitemaster

Rank Points: 902
Registered: 02-04-2003
IP: Logged

Alneyan wrote:
* 15² = 225, 14*16=224, 13*17=221 ... and a * b = [(a + b) / 2]² - [(a - b) / 2]² . I've used a form of this formula shortly after I learned multiplications in the first place, so I only have an intuitive understanding of the thing ("it's obvious"). Is the formula actually so trivial to prove and to construct? I have not been able to find a constructive proof, either by looking it up or with pen and paper, perhaps because I've taken it for granted for so long.

There's another form of this equality that's quite common. Replacing [(a + b) / 2] with x and [(a - b) / 2] with y, the equation becomes (x + y) * (x - y) = x² - y². This can be verified with ordinary arithmetic, though there's also a geometric proof:

         x     y
     |--------|--|
   - +--------+--+
   | |        |  |
x-y| |    R   |S |
   | |        |  |
   - +-----+--+--+
 y | |  T  |V |
   - +-----+--+
     |-----|--|
       x-y  y

R and S make (x + y) * (x - y); S and T are the same size, so this is the same as R and T. R, T and V make x², whereas V alone is y². Hence R and T make x² - y², proving the identity.

____________________________
Today the refrigerator, tomorrow the world!

Watcher
Level: Smitemaster

Rank Points: 902
Registered: 02-04-2003
IP: Logged

Alneyan wrote:
* While matrix multiplication is trendy, I wonder why matrix multiplication is traditionally defined as "rows in A against columns in B". It seems to me that transposing B before doing the multiplication (so "rows in A against rows in B") is easier to understand.

So, is there a loophole in the "transposing matrices" business? Or am I just the odd case who cannot work the "row against column" way, preferring to stay horizontal? If nothing else, "A X B transposed" is a lot sweeter when implementing matrix multiplication in (at least) some programming languages.

There's actually a good reason for this definition of matrix multiplication. The way it works means that if A is an m by n matrix, and B is an n by r matrix, then A * B is well-defined and an m by r matrix. This is really handy when you have products involving more than two matrices. For example, if A, B, and C are matrices, and you know that (A * B) * C is well-defined, then you immediately know that A * (B * C) is well-defined, and it can be proven to have the same value. This lets you drop parantheses in matrix products, and merely write A * B * C.

Anyway, the way I usually remember matrix multiplication is this: You want to calculate A * B. Arrange A and B like so:

+------+----+
|      | |  |
|square| |B |
|      | v  |
+------+----+
|      |    |
|----->| x  |
|  A   |    |
|      |    |
|      |    |
+------+----+

The upper left is empty and forms a square; the lower right is where the result will be placed. The arrows indicate how to find the value of x: go through this row and column, continually multiplying a number from A with a number from B, then sum up the products at the end.

____________________________
Today the refrigerator, tomorrow the world!

TripleM
Level: Smitemaster
Rank Points: 1373
Registered: 02-05-2003
IP: Logged

Alneyan wrote:
* Given any 2X2 matrix A, is there any other way besides the naive approach to calculate A^n ? (It doesn't seem so, but linear algebra only evokes scar(r)ed sophomore students for me.)

There is a much faster way than multiplying the matrix by itself n times that works for any sized matrix. But it still involves multiplying matrices in the normal way.
Basically, you just keep multiplying the matrix *by itself* several times. Then work out which of those results you need to multiply together to end up with A^n - very much like binary.
For example, if you wanted A^18, rather than doing 17 multiplications, you do this:
A*A = A^2
A^2 * A^2 = A^4
A^4 * A^4 = A^8
A^8 * A^8 = A^16
A^16 * A^2 = A^18.
Thats only five multiplications.

Anyway.

---

[Last edited by TripleM at 03-31-2007 10:17 PM]

Alneyan
Level: Smitemaster
Rank Points: 622
Registered: 07-06-2004
IP: Logged

TripleM: Thanks for your comment; I should have added somewhere "besides the standard shortcuts for exponentiation". In other words, I'm just trying to satisfy my curiosity about matrices, as I know either too much or too little about them.

Watcher wrote:
There's actually a good reason for this definition of matrix multiplication. The way it works means that if A is an m by n matrix, and B is an n by r matrix, then A * B is well-defined and an m by r matrix. This is really handy when you have products involving more than two matrices. For example, if A, B, and C are matrices, and you know that (A * B) * C is well-defined, then you immediately know that A * (B * C) is well-defined, and it can be proven to have the same value. This lets you drop parantheses in matrix products, and merely write A * B * C.

Does there exist three non-square matrices A, B and C so that (A * B) * C and A * (B * C) are well-defined? I can't find an example right now, but I guess I'm tired. Let's see if H&S syndrome works here too...

I was wondering about the whole "way to picture matrix multiplication" simply because I have a tough time picturing the "normal" process, but it all becomes trivial once I have transposed the second matrix. Odd, though it might be a side-effect of my acquaintance with functional programming... or plain weirdness. Your pick.

Watcher
Level: Smitemaster

Rank Points: 902
Registered: 02-04-2003
IP: Logged

Alneyan wrote:
Does there exist three non-square matrices A, B and C so that (A * B) * C and A * (B * C) are well-defined? I can't find an example right now, but I guess I'm tired. Let's see if H&S syndrome works here too...

Sure does. For instance, let A be 1x2, B be 2x3, and C be 3x4. Then A * B * C is a 1x4 matrix. All that matters is that the dimensions match up: A has as many columns as B has rows, and B has as many columns as C has rows. That's all it requires for A * B * C to be defined.

____________________________
Today the refrigerator, tomorrow the world!

stigant
Level: Smitemaster

Rank Points: 1182
Registered: 08-19-2004
IP: Logged

In fact, not only are (A*B)*C and A*(B*C) both defined, they are equal. Matrix multiplication has the associative property. Most 3D rendering routines are built around this principle. Matrix multiplication is not, however, commutative. A*B =/= B*A (In fact, unless A and B are square, A*B and B*A are usually not both defined).

____________________________
Progress Quest Progress

---

[Last edited by stigant at 03-31-2007 11:50 PM]

krammer
Level: Smitemaster

Rank Points: 904
Registered: 02-12-2003
IP: Logged

stigant wrote:
(In fact, unless A and B are square, A*B and B*A are usually not both defined).

Not exactly... they are both defined iff B tranposed is the same size as A. This includes the case when both are square, but also if, say, A is 2x5 and B is 5x2 - in which case AB is 2x2 and BA is 5x5.

____________________________
+++ Divide by Cucumber Error +++ Please Reinstall Universe and Reboot +++

"Oook!"

Kallor
Level: Master Delver
Rank Points: 277
Registered: 04-02-2007
IP: Logged

Hello.

Suppose A is square matrix. You can count A^n fast is A is diagonalizable: if A can be written as A=T^(-1)*D*T, where D is a diagonal matrix. Then A^n=T^(-1)*D^n*T, which is fast to count, for the n:th power of a diagonal matrix is just a diagonal matrix with diagonal elements raised to n:th power. Matrix A is diagonalizable iff its eigenvectors are linearry free. This happens every time when A:s eigenvalues are all different. You can choose A:s eigenvectors as the columns of T and eigenvalues as diagonal elements of D. If you don't know what wigenvalues are, go check it out in wikipedia or something, because they are really useful tools in matrix theory.

____________________________
Kallor

Kallor
Level: Master Delver
Rank Points: 277
Registered: 04-02-2007
IP: Logged

Ok I see that your A was 2*2 matrix. Let A be
[a b]
[c d].
Then the eigenvalues are solutions x_1 and x_2 of the equation (a-x)*(d-x)-c*d=0, and eigenvectors are vectors X_1 and X_2 such that A*X_1 = x_1*X_1 and A*X_2 = x_2*X_2. Now choose
T=[X_1 | X_2] and
D=[x_1 0 ]
[0 x_2].
If T^(-1) exists, you can count A^n fast for any n.

____________________________
Kallor