What number pyramids have one unique solution

linear algebrasystems of equations

Question

I came up with this question myself, so I don't know if it has a (nice) solution.

Consider number pyramids like this one, where two neighbouring numbers added are equal to the one on top of them. Only some of them are filled in, though.

If we are given a number pyramid of size n, and at least n spots where numbers have been put in so that it has at least one valid solution, how can we determine if it has one solution or infinitely many?

Example

We are given a pyramid of size 4 where the following spots have been filled in

          --------
          |Filled|
       ---------------
       |      |      |
   -----------------------
   |      |Filled|      |
-----------------------------
|Filled|      |      |Filled|
-----------------------------

For example they could be filled like this

          ---------
          |   15  | 
       ---------------
       |      |      |
   -----------------------
   |      |   3   |      |
-----------------------------
|   1  |      |      |   5  |
-----------------------------
Wich leads to infinitely many solutions:
          ---------
          |   15  | 
       ---------------
       | 4+a  | 11-a |
   -----------------------
   |  1+a |   3   |  8-a |
-----------------------------
|   1  |  a   |  3-a |   5  |
-----------------------------

Infact, all solvable pyramids of this kind have infinitely many solutions.

One idea I have is to interpret this pyramid as a system of linear equations with n(n+1)/2 variables. I do not now how to use this idea, though.

Best Answer

You can test whether the values uniquely determine a pyramid solution by testing whether a certain matrix is invertible.

Theorem. Consider a pyramid with height $h$ and $m\equiv h(h+1)/2$ nodes. Define the $h\times m$ ancestral path matrix $N$ as follows:

$$N_{i,j} = \text{number of distinct upward paths from the }i\text{th leaf node to node }j.$$

In other words, if you express each node's value as a sum involving just the values of the leaf nodes, $N_{i,j}$ is the coefficient of the $j$th leaf in the sum defining the value of the $i$th node. (More intuitively, each row of $N_{i,j}$ records the values of the nodes in the pyramid when one base node has value 1 and the other base nodes have value 0. These are primitive cases; every valid solution is made of multiples of these; they're a basis for the solution space.)

(!) If you fill in $h$ values of a pyramid, then those values form a unique solution to the pyramid if and only if the corresponding $h$ columns of $N$ are linearly independent.

(Note: So the uniqueness is determined solely by the placement of the $h$ variables; their values may be chosen freely.)

For example, the ancestral path matrix for height $h=3$ looks like: $$\begin{bmatrix}1&1&&1&&\\2&1&1&&1&\\1&&1&&&1\end{bmatrix}$$

(In this basis, variables are listed in "topological" order, where higher nodes come before lower nodes.) You can pick any $h=3$ columns of this matrix, corresponding to filling in any $h$ variables. Those columns are linearly independent if and only if filling in those variables will uniquely determine a solution.

Proof. A pyramid defines a homogeneous system of equations. This system can be represented as a matrix $A$. You can find a basis for the solution space by forming the augmented matrix $[A^T|I]$ and reducing it using Gaussian elimination, forming a matrix $[M | N^\prime]$. The rows of $N^\prime$ corresponding to all-zero rows of $M$ comprise a basis for the solution space (null space) of $A$. Call that submatrix $N$.

For the system of equations defining a pyramid, it is easy to prove that the null matrix $N$ is the ancestral path matrix of the pyramid. (This is because row reduction of $[A^T | I]$ always happens in a straightforward way; starting from the top of the pyramid, each parent row is added to all of its child rows. After this process is complete, the matrix is in reduced form.)

If $h$ columns of the null matrix are linearly independent, then those variables uniquely determine a solution, as described in my answer here: How to define pivot columns? .

So you can determine whether a certain set of filled in values uniquely determines a solution by selecting the corresponding columns of $N$, and computing the determinant of that submatrix. That set of values uniquely determines a solution if and only if the determinant is non-zero.

Related Question