14
$\begingroup$

This puzzle may seem off topic; though the motivation and background is somewhat mathematically technical, its solution is purely combinatorial (and quite cute).

In multivariable calculus, the main objects are are $\color{green}{\text{vectors}}$ and $\color{red}{\text{scalars}}$. There are three ways to "multiply" these together:

  • The cross product, $\times$, turns two vectors into a different vector; $\color{green}{v_1}\times \color{green}{v_2}=\color{green}{v_3}$.

  • The dot product, $\cdot$, turns two vectors into a scalar; $\color{green}{v_1}\cdot \color{green}{v_2}=\color{red}{s_1}$.

  • The scalar product, $*$, either turns a vector and a scalar (in either order) into a vector, or it turns two scalars into a scalar: $$ \color{green}{v_1}*\color{red}{s_1}=\color{green}{v_2}\qquad \color{red}{s_1}*\color{green}{v_3}=\color{green}{v_4}\qquad \color{red}{s_1}*\color{red}{s_2}=\color{red}{s_3} $$

These are the only legal uses of these operations. For example, the expression $\color{green}{v_1}\times \color{red}{s_1}$ is undefined, just like division by zero is.

An expression using these symbols may or not be legal. For example, $$ v_1 \times v_2 \cdot v_3 *v_4 $$ can be interpreted legally, if we group this as $((v_1 \times v_2) \cdot v_3) *v_4$. A different legal order of operations would be $v_1 \times ((v_2 \cdot v_3) *v_4)$. However, for the expression $$ v_1\cdot v_2\times v_3 \cdot v_4, $$ then there is no way to perform the operations in an order which is legal.

My question is this: if you are given an expression which looks like $$ v_1 \,\_\, v_2 \,\_\,v_3 \,\_\,\cdots \,\_\,v_{n-1} \,\_\, v_n $$ where each $v_i$ is a vector, and each $ \,\_\,$ is filled with either $\times,\cdot$ or $*$, what is a simple criteria to tell if it is legal? An expression is legal if there is some order of operations for which it makes sense.

The answer should not be a computer program which takes in such expressions and outputs yes or no: it should be a rule that would allow a child to tell which expressions are legal, and an explanation as to why the rule works.

Addendum: The brute force algorithm of checking every order of operations takes exponential time. Checking your "simple criteria" should take polynomial time in $n$ (since children are impatient).

$\endgroup$
  • $\begingroup$ You said no computers so I went ahead and edited that in. I hope you don't mind. $\endgroup$ – warspyking May 10 '15 at 12:28
  • $\begingroup$ Why does this have 9 upvotes? This is why we define associativity of operations. Brute force is NP, which is FACTORIAL not exponential, Factorial grows faster than exponential, we'd kill for exponential! This is elementary type checking. For example (testing Latex, going to second message) $f:\mathbb{R}^n\times\mathbb{R}^n\rightarrow\mathbb{R}$ is your dot product's signature (as a function $f$ taking two $n$-vectors) $\endgroup$ – Alec Teal May 10 '15 at 15:06
  • $\begingroup$ if we use $g:\mathbb{R}^3\times\mathbb{R}^3\rightarrow\mathbb{R}^3$ for your $\times$ the same thing applies. Your question basically becomes "what functions can we compose". This is a very useful tool for deducing "what can I do?" in mathematics. Like for example "what way round does that matrix go?" "Can I multiply this matrix and that vector" - these are answered by looking at the TYPES they operate on. $\endgroup$ – Alec Teal May 10 '15 at 15:09
  • 1
    $\begingroup$ @AlecTeal I was thinking exponential growth because the number of ways of associating $n$ operations is given by the Catalan Numbers (see the third bullet point), and these grow exponentially, at about $4^n/n^{3/2}$. $\endgroup$ – Mike Earnest May 10 '15 at 19:29
10
$\begingroup$

Let the number of dot products be $D$, and let the number of scalar products be $S$. The expression is valid if $D=S$ or $D=S+1$.

Every time you do a dot product, the number of scalars increases by $1$. Every time you do a scalar product, the number of scalars decreases by $1$. When all products have been performed, we must have $0$ or $1$ scalars left, so we must have $D=S$ for $0$ scalars left (in which case the result is a vector) or $D=S+1$ (in which case the result is a scalar).

If $D=S$ or $D=S+1$, we can perform all cross products first, then look for pairs of dot and scalar products next to each other and convert $v\cdot v*v$ to $((v\cdot v)*v)$ or $v*v\cdot v$ to $(v*(v\cdot v))$ until we just have something of the form $v$ or $v\cdot v$.

$\endgroup$
  • $\begingroup$ What about (v dot v) * (v dot v) ? D = 2, but S = 0. $\endgroup$ – Brian J May 10 '15 at 13:37
  • $\begingroup$ @BrianJ there's a star in the middle of your equation, so D = 2 and S = 1 $\endgroup$ – mdc32 May 10 '15 at 13:59
  • $\begingroup$ @mdc32 I misread, and thought S was scalar values, not scalar products. Oops. $\endgroup$ – Brian J May 10 '15 at 14:00
7
$\begingroup$

Ignore all the cross products. If there are the same number of dot and scalar products, the expression is valid and evaluates to a vector. If the number of dot products is one more than the number of scalar products, the expression is valid and evaluates to a scalar. Otherwise the expression is invalid.

Why does this work?

  1. Cross products convert two vectors into a vector. If both sides of the cross product are evaluated before the cross product, then it means that both sides are expressions that evaluate to vectors. But we can evaluate the cross product first, then evaluate the left with the result of the cross product to result in a vector, then evaluate the right with the result of the left side to result in a vector. So it is safe to evaluate cross products first.

  2. Now we only have dot products and scalar products to consider. The number of vectors to start with is 1 more than the number of operators. Each dot product evaluated reduces the number of vectors by 2, while scalar products don't change the number of vectors. If the expression is valid, we must have either 0 or 1 vectors after all the products are evaluated. This is only possible if there are as many dot products as scalar products, or one more dot product than scalar products.

  3. While there is at least one dot product and one scalar product, there must be a dot product and a scalar product next to each other. The dot product can be evaluated first, then the scalar product, reducing three vectors into one vector. We can repeat this until there is either a single vector or a single dot product of vectors left, guaranteeing that the expression can be evaluated if the number of each type of product is correct.

$\endgroup$
  • $\begingroup$ This answer is correct and well explained! I chose between accepting yours and the other by coin flip :/ $\endgroup$ – Mike Earnest May 10 '15 at 19:25
  • $\begingroup$ +1 for explicitly stating how $D-S$ (number of dot products minus number of scalar products) relates to the type of the result $\endgroup$ – Rosie F Jul 20 '16 at 6:36
1
$\begingroup$

How about "For any expression to be legal, all its subexpressions (anything that gets calculated before the final result) must use a scalar product operator iff one or both of the subexpression's subexpressions (sub-2-expressions?) evaluate to a scalar."

$\endgroup$
  • $\begingroup$ This is true, but not a simple rule. You would be hard pressed to find a child who could understand that statement. $\endgroup$ – Mike Earnest May 10 '15 at 3:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.