Wikipedia:Reference desk/Archives/Mathematics/2010 August 5

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

August 5

Countable Compact Connected Hausdorff Space

I know that there is a rather obvious proof that no nontrivial space has all these properties, just can't remember it and google isn't very helpful. It's been on the edge of my mind for a while, can anyone be of help? 66.202.66.78 (talk) 07:07, 5 August 2010 (UTC)

One proof uses the Baire category theorem. Algebraist 07:31, 5 August 2010 (UTC)

There's an easier proof: compact hausdorff are normal, so assume there are two distinct points x,y. By Urysohn's lemma there's a continuous function from X to [0,1] such that f(x)=0 and f(y)=1. Now X is connected so this function must be surjective, so X is at least continuum. Money is tight (talk) 05:43, 6 August 2010 (UTC)

how "unpredictable enough" system is useful?

From second paragraph of Experimental system, "A successful experimental system must be stable and reproducible enough for scientists to make sense of the system's behavior, but variable and unpredictable enough that it can produce useful results".

I can understand that system must be variable enough to produce useful results, but I cannot understand why system must be unpredictable enough?

Can someone give a simple explanation and example? - manya (talk) 07:38, 5 August 2010 (UTC)

If you can predict the outcome of an experiment, there is no point in performing the experiment. I know that I get wet when going out in the rain, so doing so is not much of an experiment. Bo Jacoby (talk) 08:37, 5 August 2010 (UTC).

I thought so. But I think 'variables' are input parameters, and for tested/experimented set of parameters the output is predictable because system is reproducible. For untested set of data, how do we know whether it is predictable until experiment is done? Is this 'experimental system' universal (chemistry, physics etc) or specific to bio field? How a system (that is "physical, technical and procedural basis") be predictable or unpredictable. I have been under strong impression that theory proposes (predicts) and experiment verifies (proves). - manya (talk) 10:37, 5 August 2010 (UTC)

When there are conflicting theories, an experiment settles the conflict. See for example the Bell test experiments. Bo Jacoby (talk) 11:25, 5 August 2010 (UTC).

creating diagonal matrix with only basic operations?

I would like to "convert" a vector to a diagonal matrix with the elements of the vector on the main diagonal. This can be solved with an easy loop, but the problem is, that I need to do it by using only basic mathematical operations: multiplication and addition (to transpose is allowed), as I need those matrices as variables in a function which I intend to derive, integrate, etc. I originally needed to do an element-wise multiplication (like A .* B instead of A * B in Matlab), so I tried the following:

[A;B;C] * Q * [X;Y;Z] = [AX;BY;CZ]

What I would like to have is a Q which transforms [A;B;C] to [A 0 0; 0 B 0; 0 0 C] The problem was, if I wrote it as Q = [1 1 1] * W (just to have a 3*3 matrix) the

[A A A; B B B; C C C] * [a b c; d e f; g h i] = [A 0 0; 0 B 0; 0 0 C] 

system does not have a solution: we get contradictions like a+d+g=1 and a+d+g=0

Does this mean that this is unsolvable? Or is my approach wrong? Actually, as the vectors can be quite big, I would prefer a solution to the elementwise multiplication without using square matrices, if possible at all, I just couldn't find one. --131.188.3.20 (talk) 10:40, 5 August 2010 (UTC)

There is no matrix Q such that $xQ$ is the diagonal matrix with x on the diagonal. This is easy to see; the rank of x, and hence xQ, is at most 1, while the rank of a general 3x3 diagonal matrix is 3.

I can't understand why you need this, so maybe you should explain your application a bit more. -- Meni Rosenfeld (talk) 11:38, 5 August 2010 (UTC)

I just need what I described in the introduction: to do an element-wise multiplication (like .* in Matlab) with basic arithmetical operations. It is enough if I find a solution for vectors. So the goal: given two vectors A and B, construct a vector C where each element C_i is A_i*B_i . What is important, to do it in such a way, that I can use it fo perform algebraic operations and even some calculus at the end. Otherwise it would be easy to write a program that loops through the vector. --131.188.3.21 (talk) 14:48, 5 August 2010 (UTC)

Element-wise multiplication is the basic arithmetical operation, also known as Hadamard product. There's no way to reduce it to "more basic" arithmetic operations. You just write $C=A\circ B$ and continue to do whatever you want. For example, if A and B are functions of t, you have ${\frac {dC}{dt}}={\frac {d(A\circ B)}{dt}}=A\circ {\frac {dB}{dt}}+B\circ {\frac {dA}{dt}}$. -- Meni Rosenfeld (talk) 15:32, 5 August 2010 (UTC)

Wow, thanks for the idea. So I can do anything with it, I mean to play around with it in equations like it was just a "normal" multiplication? The no way to reduce it means that it is impossible to build if out of other operations, and I can give up searching for it? Our article does not tell much about it. --131.188.3.21 (talk) 15:45, 5 August 2010 (UTC)

You can build it from other operations, but as an informal observation, they won't be more basic and I doubt they'll help you in manipulating it. For example, you can define a linear transformation $f:\mathbb {R} ^{3}\to \mathbb {R} ^{3\times 3}$, $f(x)$ is the diagonal matrix with x on the diagonal. Then you'll have $A\circ B=f(A)B$, but doing calculus with this will be tricky at best. You certainly can think about other creative ways to construct it.

This operation is in many ways similar to ordinary multiplication of numbers. Common sense is usually enough to tell what will or won't work with it, and where that fails proving basic properties should be fairly simple. -- Meni Rosenfeld (talk) 15:57, 5 August 2010 (UTC)

The derivation gives me headaches: if I have $(AX)\circ B$, where A and B are constants and X varies in t, and the AX has the same dimensions as B, but A or X alone don't, than deriving it will lead me to $B\circ A$ which is not possible. Unless I got something wrong. --131.188.3.20 (talk) 00:28, 6 August 2010 (UTC)

${\frac {d((AX)\circ B)}{dt}}={\frac {d(AX)}{dt}}\circ B=\left(A{\frac {dX}{dt}}\right)\circ B.$

In case this was the problem, note that element-wise multiplication is not "associative with" matrix multiplication. In general $(AB)\circ C\neq A(B\circ C)$. By itself it's commutative and associative, though. So you can write the above as $B\circ \left(A{\frac {dX}{dt}}\right)$, but not as $(B\circ A){\frac {dX}{dt}}$. -- Meni Rosenfeld (talk) 06:25, 6 August 2010 (UTC)

Yes, I knew (I mean, I suspected and proved for myself with counterexamples) they are not associative, but the problem lies elsewhere. I think I made a mistake with the notation. Let x be a vector and I want to derive by x. ${\frac {d((Ax)\circ B)}{dx}}$ will lead to $A\circ B$, but what if the dimensions of A and B are different? Like, for example, x is a n*1 vector, and B an m*1, and A an m*n matrix. —Preceding unsigned comment added by 131.188.3.20 (talk) 08:40, 6 August 2010 (UTC)

I think these cases work if you extend the meaning of $\circ$ so that, for example, ${\begin{bmatrix}a&b\\c&d\end{bmatrix}}\circ {\begin{bmatrix}e\\f\end{bmatrix}}={\begin{bmatrix}ae&be\\cf&df\end{bmatrix}}$ and so on. Note that matrix multiplication and element-wise multiplication correspond to two very different ways of interpreting matrices (either as linear transformations or as just a bunch of numbers), and so the results might not always be elegant when you try to use them together.

If you haven't already, you may want to look at Matrix calculus which discusses differentiating with respect to a vector (though not in relation to the Hadamard product). -- Meni Rosenfeld (talk) 09:32, 6 August 2010 (UTC)

This interpretation is useful, but I don't see what to do with a ${\begin{bmatrix}a\\b\end{bmatrix}}\circ {\begin{bmatrix}c\\d\\e\end{bmatrix}}$

To turn in into ${\begin{bmatrix}ac\\bd\end{bmatrix}}$ or ${\begin{bmatrix}ac\\bd\\0\end{bmatrix}}$ does not make any sense, as the original purpose of A was to make a surjective mapping of "smaller" vector x onto the bigger vector B, so if I just pair first with first and so on, the pairings will not make any sense. (I'm sorry I'm not that good in using the English terminology, but I hope I was understandable) --131.188.3.21 (talk) 10:00, 6 August 2010 (UTC)

Oops, I mean, in this case it should have been $A\circ B$ not $x\circ B$ Still, the problem above can come up: A is just a matrix to reorder the elements of x, so it does not make much sense to multiply it to elements of B. --131.188.3.20 (talk) 10:22, 6 August 2010 (UTC)

Why not? In your case B specifies by what values to multiply each entry of $Ax$. So it makes sense that instead of multiplying by B after reordering, you preemptively multiply it by A in preparation for the imminent multiplication with x.

It's possible that the notation should be extended in additional ways in order to deal with more general cases. -- Meni Rosenfeld (talk) 11:37, 6 August 2010 (UTC)

Thank you, you was very helpful, now I know how to do derivations with the element-wise product :) . However, there are still things that baffle me: it seems very hard to reorder and separate variables, like getting x in $Ax\circ B+Cx\circ D$. Is there any good source you suggest me to read about the properties of the pointwise product? What I found gave very little useful information about its properties. What I found out by testing is that it's not only not associative but not even distributive with other common operations. --131.188.3.21 (talk) 12:51, 6 August 2010 (UTC)

Not that I know of. The PlanetMath entry has some basic info and references. -- Meni Rosenfeld (talk) 13:21, 6 August 2010 (UTC)

Conjectures

What will happen if P=NP, or the Riemann hypothesis is false, or some other conjecture that's obviously true is disproved? --138.110.206.101 (talk) 12:47, 5 August 2010 (UTC)

Some people will be surprised. (In the mean time, you'd be hard pressed to find a mathematician who thinks these are "obviously true".) Staecker (talk) 13:56, 5 August 2010 (UTC)

Just about everyone agrees that P!=NP and the Riemann hypothesis is true; many "theorems" are proved based on assuming them. If P=NP or the Riemann hypothesis is false, these would all be invalidated. --138.110.206.150 (talk) 19:45, 5 August 2010 (UTC)

What will happen? (1) Clay will be 1,000,000 dollars poorer, and (2) the reference desk will be flooded with requests for explanation. Tkuvho (talk) 20:12, 5 August 2010 (UTC)

Are there that many theorems assuming P ≠ NP? Oliphaunt (talk) 21:12, 5 August 2010 (UTC)

Most mathematicians think those are the most likely possibilities, but they are far from certain about it. --Tango (talk) 22:09, 5 August 2010 (UTC)

Did you take a look at our articles on this? From P versus NP problem: "Is P equal to NP? In a 2002 poll of 100 researchers, 61 believed the answer to be no...". 61% is hardly "just about everyone", and "believed" is not the same as "were certain", let alone "think it obvious". From Riemann hypothesis: "The consensus... is that the evidence for it is strong but not overwhelming... there is some reasonable doubt about it."

The converse exists as well - there are many theorems that assume that P=NP, if it turns out P!=NP then those will be moot. So what? Everyone knows that these theorems are conditional on whether P=NP. It's not like things that were thought to be true will turn out false, it's that things that were thought to be maybe true will turn out false and others to be actually true. -- Meni Rosenfeld (talk) 06:40, 6 August 2010 (UTC)

Axiom of choice again

This is related to the axiom of choice question I asked a few days back. Suppose we have a relation R on a set A. Suppose further that R is both reflexive and symmetric. I want to find out a cover of the set A, i.e. a collection of nonempty sets A_i such that their union is A, from this relation. The obvious thing seems to pick an x, and define A_x as the set of all y such that (x,y) is in R. Now if this exhausts the set we are done, if not then we pick up another element and continue. My question is what guarantees this procedure is valid. Does the axiom of choice ever enter into the picture and if so, what is the choice function?-Shahab (talk) 13:48, 5 August 2010 (UTC)

What do you want the procedure to produce? Some condition seems to be missing in the description, because you can trivially construct a cover of A by taking A₀ = A.—Emil J. 13:58, 5 August 2010 (UTC)

Describing this as an iterative procedure (pick an x, then form etc.) is a good heuristic tool, but it may be misleading. For example, if the set of equivalence classes is uncountable, obviously you cannot choose your x's one-by-one. What is happening here is that you are forming all the equivalence classes simultaneously. The axioms of ZF are sufficient for this, as already pointed out by algebraist in the previous discussion. On the other hand, if you want to index by elements of A, you need choice, as already discussed. Tkuvho (talk) 14:15, 5 August 2010 (UTC)

The cover needs to be related to the relation-Shahab (talk) 14:13, 5 August 2010 (UTC)

Related in what way?—Emil J. 14:25, 5 August 2010 (UTC)

I am sorry if my explanation wasnt clear enough.What I want is that each class (I'll call it compatible class, as apparently a symmetric and reflexive relation goes under the name compatible relation) is such that there is an element x in it so that all y, for which we have xRy, are in the same class, and x isnt in any other class. Will simultaneously defining all the classes as [x] = {y: xRy} guarantee this? or I will have to proceed step by step, in which case do I need choice, and how?-Shahab (talk) 14:28, 5 August 2010 (UTC)

No, that won't work. Try the set {A,B,C} with the relation {(A,B),(A,C)}. Your method would give the cover {A,B,C}, {A,B}, {A,C}. Since every element is in at least two sets in the cover, there is no way you can have an x for each set that isn't in any other set. --Tango (talk) 14:43, 5 August 2010 (UTC)

Note that the relation is given to be reflexive and symmetric, which isnt the case in your example. Regards-Shahab (talk) 14:48, 5 August 2010 (UTC)

I know, I just realised that. It's just my bad notation. I meant the smallest relation containing that relation and satisfying the conditions given, but my notation obviously doesn't actually say that. --Tango (talk) 15:05, 5 August 2010 (UTC)

Okay. I see what you mean.-Shahab (talk) 15:20, 5 August 2010 (UTC)

Equivalence relation and partitions

Resolved

Okay here is another problem. Let R be an equivalence relation on A and {A₁,...A_k} be a set of subsets on A such that A_i is not a subset of A_j for i≠j and such that a and b are contained in one of the subsets if and only if the ordered pair (a,b) is in R. I need to show that {A₁,...A_k} is a partition of A.

I can see that it covers A but why are all A_i's disjoint. Thanks-Shahab (talk) 15:35, 5 August 2010 (UTC)

I don't think they are necessarily disjoint. Let A={0,1,2,3,4,5} and aRb iff a=b (mod 2). Then let the A_i's be {0,2}, {0,4}, {2,4}, {1,3}, {1,5}, {3, 5}. That seems to satisfy your requirements, but the subsets aren't disjoint. --Tango (talk) 16:43, 5 August 2010 (UTC)

Thanks. It is an error in the book I am reading then, which contains this question. A kind of relief indeed!-Shahab (talk) 17:02, 5 August 2010 (UTC)

The book definitely says "Prove" and not "Prove or provide a counter-example"? You should check that my counter-example does work, I may have made a mistake or misunderstood the question (especially since I've heard it 2nd hand). --Tango (talk) 17:13, 5 August 2010 (UTC)

Yes, I checked it. Your example is right. The problem is from this book (Page 173).-Shahab (talk) 17:32, 5 August 2010 (UTC)

Did you quote the problem exactly? The link you provided does not offer any preview of the book. -- 119.31.121.87 (talk) 00:14, 6 August 2010 (UTC)

Strange, it does so in my browser--Shahab (talk) 03:15, 6 August 2010 (UTC)

Perhaps it is an issue with being in Thailand, although it simple says "No preview available" and does not mention geographic restrictions. -- 112.142.27.47 (talk) 13:14, 6 August 2010 (UTC)

I get the same message in the UK. --Tango (talk) 16:22, 6 August 2010 (UTC)