Joined: 12/28/2007
Posts: 235
Location: Japan, Sapporo
Bobo the King wrote:
Bobmario511 wrote:
Saw this abstract linear algebra question on a test today and wanted to share it (posting it off of memory so somethings may be off):
Let A,B,M be nxn matricies which have real entries where n is a natural number, where AM=MB [corrected] and A and B share the same characteristic polynomial.
Prove det(A- MX) = det(B - XM) if X is an nxn matrix with real entries.
It's not specified whether this is true for any X or if there merely exists an X. I'll assume you mean there exists an X because that's the proof I'm coming up with.
My proof relies on M being invertible, which wasn't specified. I suppose you might be able to re-work it in such a way that it doesn't require inverting M. I kind of doubt it, though, since M-1 shows up explicitly in my solution.
A and B are similar because B = M-1AM. So that's neat.
Also, we know det(A-λI) = det(B-λI). That's more useful. Let's start there.
det(A-λI) = det(B-λI)
Replace I on the left with MM-1. Replace I on the right with M-1M:
det(A-λMM-1) = det(B-λM-1M)
Now just commute λ on the left hand side because it is a scalar.
det(A-MλM-1) = det(B-λM-1M)
Finally, identify X as λM-1. Now we have
det(A-MX) = det(B-XM)
QED.
When M is regular, we can prove it for any X. In fact, we have det(A-MX)det(M) = det(AM-MXM) = det(MB-MXM) = det(M)det(B-XM), and since det(M) is nonzero, we conclude det(A-MX) = det(B-XM). This is easy.
When we want to prove the existence of a non-trivial X (with M arbitrary), one of the answers is X=A (or B), for example. In fact, we have det(A-MA) = det(I-M)det(A) and det(B-AM) = det(B-MB) = det(I-M)det(B). By assumption det(A) = det(B). Thus det(A-MA) = det(B-AM). I think even this is easy.
I'm now trying to prove the general case, but only got some special cases, such as M being the direct sum of a regular matrix and a zero matrix. The point is, I guess, the case of M nilpotent.
Retired because of that deletion event.
Projects (WIP RIP): VIP3 all-exits "almost capeless yoshiless", VIP2 all-exits, TSRP2 "normal run"
I think the problem can be generalized: If you have two curves of finite length on a plane, if you evenly scale the whole thing larger or smaller (I don't know how to express this mathematically) the ratio of the lengths of those two curves remains the same. The ratio between a circumference and diameter is just a special case of this.
Of course proving this general case might not be trivial.
Joined: 12/28/2007
Posts: 235
Location: Japan, Sapporo
Warp wrote:
I think the problem can be generalized: If you have two curves on a plane, if you evenly scale the whole thing larger or smaller (I don't know how to express this mathematically) the ratio of the lengths of those two curves remains the same. The ratio between a circumference and diameter is just a special case of this.
Of course proving this general case might not be trivial.
First we have to specify what we mean by curve and by length. As long as a curve is defined as a continuous mapping [a,b] → R^2 and its length is defined to be the "limit" of the length of line segments which approximate the curve, the assertion is a consequence of the elementary facts:
d(rx,ry) = r*d(x,y) for any points x and y and any scalar r;
d(x-z,y-z) = d(x,y) for any points x, y and z,
where d(x,y) denotes the distance of x and y. If you want to go with another set of definition, let us know what it is.
Retired because of that deletion event.
Projects (WIP RIP): VIP3 all-exits "almost capeless yoshiless", VIP2 all-exits, TSRP2 "normal run"
What is the integral of sin(x)*cos(x) dx ?
a) sin2(x) / 2 + C
b) -cos2(x) / 2 + C
c) -cos(2x) / 4 + C
You can derive each alternative or:
sin(2x) = 2*sin(x)*cos(x)
sin(x)*cos(x) = sin(2x)/2
integral of sin(x)*cos(x) dx = 1/2 * integral of sin(2x) dx
Let u be 2x, then du = 2 dx:
= 1/2 * integral of sin(u) * (1/2) du
= 1/4 * integral of sin(u) du
= 1/4 * (- cos u) + C
= -1/4 * cos(2x) + C
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
If this has a solution, it has to be sqrt 2, since (sqrt 2) ^ 2 = 2
But I don't know how exactly how to prove it is the solution. I guess the partial result would increase slowly as you are adding '^x's, and when it gets to 2 it stops growing, so sqrt 2 ^ (sqrt 2 ^ (sqrt 2 ^ (...) 2))) = 2
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Ah, now I see that lim to infinity n^(1/n) = 1. I thought it would diverge to infinity for some reason.
So a general solution for x^x^x^x(...) = a is x = a^(1/a)
This infinite tower can be defined recursively, as follows:
a(1) = x
a(n +1) = x^a(n), for all n.
f(x) = limn->∞a(n)
This'll only converge if e^(-e) <= x <= e^(1/e)
http://mathworld.wolfram.com/PowerTower.html
The answer is indeed sqrt(2).
What is the integral of sin(x)*cos(x) dx ?
a) sin2(x) / 2 + C
b) -cos2(x) / 2 + C
c) -cos(2x) / 4 + C
You can derive each alternative or:
sin(2x) = 2*sin(x)*cos(x)
sin(x)*cos(x) = sin(2x)/2
integral of sin(x)*cos(x) dx = 1/2 * integral of sin(2x) dx
Let u be 2x, then du = 2 dx:
= 1/2 * integral of sin(u) * (1/2) du
= 1/4 * integral of sin(u) du
= 1/4 * (- cos u) + C
= -1/4 * cos(2x) + C
What you stated is mathematically correct, but take a look at the given choices again.
The joke is that all three choices are correct.Warp wrote:
Solve x^x^x^... = 2.
(That's an infinite power series.)
If there exists such an x, then it must satisfy x^2=2. It can't be -sqrt(2) since (-sqrt(2))^(-sqrt(2)) doesn't exist in reals (let's not go into complex here) so the only possibility is sqrt(2).
Proof that sqrt(2)^sqrt(2)^... = 2:
Consider sqrt(2)^x - x. It is decreasing on (-∞,2], since its derivative ln(sqrt(2))*sqrt(2)^x - 1 is negative on (-∞,2]. Furthermore sqrt(2)^2=2. Therefore sqrt(2)^c>c for all c<2.
However, sqrt(2)^c < sqrt(2)^2 = 2 for all c<2.
Therefore the sequence sqrt(2), sqrt(2)^sqrt(2), sqrt(2)^sqrt(2)^sqrt(2), ... is strictly increasing and bounded above by 2. Therefore it converges to some number in (-∞,2]. Furthermore, it must converge to 2, since 2 is the only number c in (-∞,2] for which sqrt(2)^c=c.
(By the way, limit (sqrt(2)^sqrt(2)^sqrt(2)^...) = sqrt(2)^(limit sqrt(2)^sqrt(2)^...) since sqrt(2)^x is a continuous function.)
What you stated is mathematically correct, but take a look at the given choices again.
The joke is that all three choices are correct.
I didn't even pay attention to the alternatives and feel stupid now..
Yeah, it was a "trick question" of sorts. :P
One way to see that all the answers are correct is to derive them and see that they all give the same result, ie. sin(x)*cos(x).
An often repeated fact of mathematics is that just because a conjecture seems to hold for a very large amount of values, that doesn't mean that it's true. And to demonstrate this, there are examples of such conjectures which have been made, and seemed to hold for really large amounts of values, but ended up being false conjectures after all.
The most typical example of this is the Pólya conjecture: If we partition all natural numbers up to some n into those with an odd number of prime factors and those with an even number of them, it seems to be that there are always more of them in the odd side than the even side. This was conjectured to be so. But it turned out to be false. And the smallest n for which it's false is 906150257.
The offset logarithmic integral function Li(x) is a function that approximates the prime-counting function π(x). (In mathematical notation, π(x) ∼ Li(x).) It was noticed that it seems that Li(x) always gives larger values than the actual prime-counting function, and this is true for a staggeringly large amount of values. Thus it was conjectured that it's always so. However, once again, this is not true. It has been proven that for an x somewhere between 1017 and 10316 Li(x) becomes smaller than π(x).
The smallest possible counter-example to the Euler's conjecture for k=4 is: 958004 + 2175194 + 4145604 = 4224814
I was wondering if there are any other seriously proposed conjectures which seem to hold for very large amounts of values, but which nevertheless have a counter-example (which is very large).
Some other examples (which you may wish to Google for more info):
The Mertens Conjecture is false, but the smallest counterexample is at least 1014 and may be as large as 101040.
A computer search of Happy numbers might lead one to think that there are never more than five of them in a row. The smallest such example of five consecutive happy numbers is {44888, 44889, 44890, 44891, 44892}. The smallest run of six consecutive happy numbers, meanwhile, starts at 7899999999999959999999996, and it has in fact been proven that for any number N, there are N consecutive happy numbers, though the smallest example grows very rapidly as a function of N.
In addition to these examples, there are many unsolved mathematical problems which, if they have a counterexample, it is very large indeed. For example, if there are any counterexamples to the Riemann Hypothesis, they are not among the first 1013 non-trivial zeroes. Any counterexample to the Goldbach Conjecture is at least 4 x 1018. If odd perfect numbers exist then the smallest one is at least 101500.
Simon Singh in Fermat's Last Theorem gives the example that all of the following are prime: 31, 331, 3331, 33331, 333331, 3333331, 33333331. But 333333331 is divisible by 17.
Joined: 4/20/2005
Posts: 2160
Location: Norrköping, Sweden
What is the formula (or a piece of pseudocode would work just as fine) for creating all the possible ways of sorting k objects into n bins (with no regard to the order they are placed)? For example for k=2 and n=3 I want to generate the matrix
0 0 2
0 1 1
0 2 0
1 0 1
1 1 0
2 0 0
I found it quite easy to find the solutions with a brute force method for small n and k, but when n and k get large it gets trickier.
Note that I'm interested in the indivudal solutions, and not just the number of solutions. I feel like there is an easy solution to this that I can't see/remember clearly...
Joined: 12/28/2013
Posts: 396
Location: Rio de Janeiro, Brasil
Each way of sorting the objects corresponds to a solution of a1 + a2 + a3 (...) + an = k, with every variable natural.
Since there is no general formula for diofantine equations, I don't think there is a simple general solution for this. With big n and big k, there will be tons of possibilities, so it's pretty much impossible to express all them in a 'simple' way.
In order to do this automatically one would have to write a code that gets all solutions to that diofantine equation. It should be possible, but I have no idea how to do it as I don't know programming.
What is the formula (or a piece of pseudocode would work just as fine) for creating all the possible ways of sorting k objects into n bins (with no regard to the order they are placed)? For example for k=2 and n=3 I want to generate the matrix
0 0 2
0 1 1
0 2 0
1 0 1
1 1 0
2 0 0
I found it quite easy to find the solutions with a brute force method for small n and k, but when n and k get large it gets trickier.
Note that I'm interested in the indivudal solutions, and not just the number of solutions. I feel like there is an easy solution to this that I can't see/remember clearly...
Ah, this type of problem is often encountered in statistical mechanics. The traditional treatment is to use the "stars and bars" method in which the stars represent the objects and the bars represent the "walls" separating the bins. So let's start with your first example, which you already seem to have a good grasp of. In this representation, the six possibilities become
||**
|*|*
|**|
*||*
*|*|
**||
and these correspond exactly to the answer in your post.
Now, I've never been all that good at writing algorithms, so I'll sketch out the gist of the algorithm as I see it:
1. Try to move the rightmost star one space to the left by exchanging its place with a bar to its immediate left.
2. If you cannot do this because there is a star to its left, try to move that star to its left by exchanging its place with a bar. Keep doing this until you find a star with a bar to its left.
3. Once you find a star that can be moved left, move all stars on its right fully to the rightmost position.
4. Continue in this manner until all stars are on the left and all bars are on the right.
For example, let's consider what this process looks like when sorting 3 objects among 4 bins:
|||***
||*|**
||**|*
||***|
|*||**
|*|*|*
|*|**|
|**||*
|**|*|
|***||
*|||**
*||*|*
*||**|
*|*||*
*|*|*|
*|**||
**|||*
**||*|
**|*||
***|||
That's 20 different configurations and we expect 6 choose 3 = 20 configurations, so they should all be present and accounted for.
I remember trying to make an algorithm that gives all possible sortings of k objects into n bins. It's like what Bobo the King described, but without the stars-and-bars aspect of it.
Bobo the King wrote:
1. Try to move the rightmost star one space to the left by exchanging its place with a bar to its immediate left.
2. If you cannot do this because there is a star to its left, try to move that star to its left by exchanging its place with a bar. Keep doing this until you find a star with a bar to its left.
3. Once you find a star that can be moved left, move all stars on its right fully to the rightmost position.
4. Continue in this manner until all stars are on the left and all bars are on the right.
How it works in the original formulation (no stars-and-bars):
Start with 0 0 ... 0 k (n bins). At each step, take the rightmost nonzero number m and note its bin number (1 to n from left to right) and call it c. If c=1, stop. Otherwise, add 1 to bin c-1, set bin c to 0 and set bin n to m-1. Note that the algorithm generates all the solutions in lexicographic order (the next one is always lexicographically later than the previous) and the last one is k 0 ... 0 0, which is when c=1.
Joined: 4/20/2005
Posts: 2160
Location: Norrköping, Sweden
Thanks a lot, Bobo and FractalFusion.
Bobo, a small question on your solution, would an equivalent (and in my eyes simpler) description of the routine be to start with your string |||*** and then look for the rightmost instance of the string |* and replace it with *|? The routine would stop when the string |* is not found. It seems to me that this will generate the same solution as you presented.
would an equivalent (and in my eyes simpler) description of the routine be to start with your string |||*** and then look for the rightmost instance of the string |* and replace it with *|? The routine would stop when the string |* is not found. It seems to me that this will generate the same solution as you presented.
No. From Bobo's first example, the string
|**|
progresses to:
*||*
But your algorithm instead progresses it to:
*|*|
and will miss the *||* configuration.
While it's quite inefficient, one way that would guarantee getting every combination would be to create an algorithm that first creates all the length-n strings of stars and bars (2^n combinations), then counts the number of stars in each string and returns the strings with exactly m of them.
Thanks a lot, Bobo and FractalFusion.
Bobo, a small question on your solution, would an equivalent (and in my eyes simpler) description of the routine be to start with your string |||*** and then look for the rightmost instance of the string |* and replace it with *|? The routine would stop when the string |* is not found. It seems to me that this will generate the same solution as you presented.
Piling on to what rhebus said, your method will work if you also move all stars to the right of |* to the rightmost position. The point is that |* --> *| can't be the only step in the algorithm. I like your simplification, though. Like I said, I've never been all that adept at writing or explaining algorithms efficiently.
Originally (as far as I know) the number e (ie. 2.71828...) came up in compound interest calculations.
For example, if you have 1 dollar, and a compound interest of 100% per year, and the interest is continuously calculated, after one year you'll have exactly e dollars.
The generic formula for this is (1+1/n)n, where n is the amount of times compound interest is calculated during the year. As n approaches infinity (which means it's continuously calculated), that formula approaches e.
Is the fact that ex is its own derivative just a coincidence, or is there a correlation with the above?
