Tagged as challenge, math

Written on 2018-02-10

## Prerequisites

The symbol $\mathbb{Z}^n$ denotes the set of all coordinate $n$-tuples with integer components. These are one kind of **$n$-dimensional lattice**.

Given two points $s=(s_1,\ldots, s_n)$ and $e=(e_1, \ldots, e_n)$, their **taxicab distance** is $$\Vert s-e\Vert_1 := \sum_{i=1}^n\vert s_i-e_i\vert.$$

Given a complex number $z$, we denote its **normalization** as
$$\operatorname{N}(z) :=
\begin{cases}
0 & \text{if }z=0,\\
z/\vert z\vert & \text{otherwise.}
\end{cases}
$$

## Challenge

A staircase path between two points, informally, is any path by going only right or up.

Formally, given the starting point $s \in\mathbb{Z}^n$ and ending point $e \in\mathbb{Z}^n$ with $s\leq e$ (i.e., each component of $s$ is less than or equal to each corresponding component of $e$), a **staircase path** is a sequence of $\ell:=1+\Vert s-e\Vert_1$ coordinates $\sigma_0,\ldots,\sigma_{\ell}$ with the following facts:

$\sigma_0 = s$,

$s\leq \sigma_k \leq e$ (in the sense described above), and

exactly one component of $\sigma_{k+1} - \sigma_k$ is $1$, with the other $n-1$ components equal to $0$.

Denote the **set of all staircase paths** from $s$ to $e$ as $\{s\to e\}$.

**Part 1**: Verify that facts 1–3 imply $\sigma_{\ell} = e$.

Next, consider the set $\mathbb{T}^{m\times n}$ defined as $n\times m$ matrices whose entries are complex numbers of unit modulus. For consistency with the above, let's suppose the bottom-left element of each matrix is identified by $(1,1)$ and top-right element is $(n, m)$.

**Part 2**: Implement the function
$$f : \mathbb{T}^{m\times n}\to \mathbb{T}\cup\{0\}$$
defined by
$$f(M) := \operatorname{N}\left(\sum_{\Sigma\in\{(1,1)\to(m,n)\}}\prod_{(x,y)\in\Sigma} M_{x,y}\right).$$

**Extra Credit**: Generalize $f$ to work on a tensor of any order.