Wikipedia:Reference desk/Archives/Mathematics/2011 October 8

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.

October 8

automating interpreting projections.

Let's say that I have I have a volume that is 3 units in the x direction, by 4 units in the y direction by 5 units in the z direction. Some number of the 60 possible blocks are filled in and it is viewed each side and the block "paths" in each direction are simply marked with whether they have a block path in them or not. So viewed from the x-y side you have a 3x4 matrix of 1s and 0s (1 = block), from the y-z side a 4x5 matrix and from the z-x side a 5x3 matrix (going around a single corner). Is there some way to analyze a set of the three matrices (some type of matrix "multiplication") to determine there exists at least one combination of the 60 blocks which fulfills it? And is there any way to determine if a connected (on the faces) combination of the 60 blocks exists which fulfills it?Naraht (talk) 02:23, 8 October 2011 (UTC)

Testing all 2 to the power of 60 possibilities would work, so in a strict sense, the answer is definitely yes. But you're most likely asking for a computationally feasible solution and/or one that would make sense to a human. 96.46.200.119 (talk) 03:13, 8 October 2011 (UTC)

Here's a solution that would work, but it's not anything to do with matrix algebra, as far as I can tell. It doesn't deal with the connectedness question. Place an imaginary block at all locations (i,j,k) such that each of (i,j), (i,k) and (j,k) are in the required projections. This is the largest set of blocks that could possibly work (in the sense that any set that works must be contained in this set). All three projections are subsets of the required sets. If at least one is a proper subset, then the problem can't be solved. Otherwise, the set you've chosen solves the problem. 96.46.200.119 (talk) 03:24, 8 October 2011 (UTC)

Assume there is a solution. To solve the connectedness part, take your big solution from before, which might not be connected. If there is a connected solution, it's contained in your big solution, and it can't be divided among the connected components of your big solution. Therefore it's contained in one of these connected components. Since the connected component is intermediate between your small connected solution, which has the right projections, and the original big solution, which has the right projections, the connected component must itself have the right projections. So it's enough to test each of the connected components of the big solution and see if any of them work. Otherwise, there's no connected solution. 96.46.200.119 (talk) 03:37, 8 October 2011 (UTC)

Create one boolean variable for each block: $b_{1,1,1}$, $b_{1,1,2}$, ..., $b_{3,4,5}$. Then the problem can be written as a set of boolean equations. A path with a block will give you an equation like $b_{1,1,1}\lor b_{2,1,1}\lor b_{3,1,1}=true$ (type 1), while a path without a block will give you an equation like $b_{1,1,1}\lor b_{2,1,1}\lor b_{3,1,1}=false$ (type 2). Equations of type 2 tell you to set all the variables they contain to false. Use this to simplify the equations of type 1. If you end up with a contradiction (false = true) then the problem is impossible. Otherwise the problem is possible and a solution is to set all the remaining variables to true. 98.248.42.252 (talk) 03:51, 8 October 2011 (UTC)

Yes, you're right, this does have a matrix interpretation. Call the matrices A=(a_ij), B=(b_jk) and C=(c_ki). Say that (i,k) is in the required xz-projection (i.e. c_ki = 1), and we want to test whether (i,k) is in the x-z projection of the big test set above. Since (i,k) is in the given xz-projection, this will happen if and only if there is some j for which (i,j,k) is in the big test set, that is, a_ij and b_jk are both 1 (since we already know c_ki = 1). This is equivalent to saying that AB has a nonzero (i,k)-entry. Thus the condition that the xz-projection is right is that AB and the transpose of C have nonzero entries in the same locations has a nonzero entry in each location where C does. Thus there is a solution if and only if AB and C^t (resp. BC and A^t, resp. CA and B^t) have nonzero entries in the same places satisfy the condition that wherever the second matrix has a one, the first has a nonzero entry. You need to calculate the three matrix products and check those conditions. Concisely, AB - C^t, BC - A^t and CA - B^t must all have nonnegative entries. I don't know for the connectedness part.96.46.200.119 (talk) 04:05, 8 October 2011 (UTC)

Series identity

Define $y:=\sum _{k=0}^{\infty }{\binom {\alpha }{k}}x^{k}$ Prove the identity $(1+x){\frac {dy}{dx}}=\alpha y$.

Ostensibly simple. I have

${\frac {d}{dx}}\sum _{k=0}^{\infty }{\binom {\alpha }{k}}x^{k}$

$=\sum _{k=1}^{\infty }{\binom {\alpha }{k}}kx^{k-1}$

$=\sum _{k=0}^{\infty }{\binom {\alpha }{k+1}}(k+1)x^{k}$

$=\sum _{k=0}^{\infty }{\frac {\prod _{j=0}^{k}(\alpha -j)}{(k+1)!}}(k+1)x^{k}$

$=\sum _{k=0}^{\infty }{\frac {\prod _{j=0}^{k}(\alpha -j)}{k!}}x^{k}$

$=\alpha \sum _{k=0}^{\infty }{\frac {\prod _{j=1}^{k}(\alpha -j)}{k!}}x^{k}$

Can someone manoeuvre this expression into ${\frac {\alpha }{1+x}}\sum _{k=0}^{\infty }{\binom {\alpha }{k}}x^{k}$? Widener (talk) 03:49, 8 October 2011 (UTC)

This doesn't answer your last question, but it is well known that your series represents the function (1+x)^(alpha), so the identity can be proved by differentiating this function. 96.46.200.119 (talk) 04:10, 8 October 2011 (UTC)

The proof that $\sum _{k=0}^{\infty }{\binom {\alpha }{k}}x^{k}=(1+x)^{\alpha }$ is usually done by proving the identity above and then solving it as a differential equation. Ultimately you have to prove the identity above independently of $\sum _{k=0}^{\infty }{\binom {\alpha }{k}}x^{k}=(1+x)^{\alpha }$ Widener (talk) 04:21, 8 October 2011 (UTC)

All right. I learned this theorem using a different argument, but I understand that for your purposes you need an independent proof.

Straightforward calculations from your expression for y' will give you

$(1+x)y'=\sum _{k=0}^{\infty }\left[(k+1){\binom {\alpha }{k+1}}+k{\binom {\alpha }{k}}\right]x^{k},$

so it's enough to check that the kth coefficient appearing here is actually equal to

$\alpha {\binom {\alpha }{k}}.$

I don't want to write it out, but this is very straightforward, seeing as the two binomial coefficients have almost all the same factors, except for a few, so the calculation can be started by taking out these common factors.96.46.200.119 (talk) 04:37, 8 October 2011 (UTC)