On vectors shifted by $1$?

Question

Denote $u\leq v$ to imply vector $u$ lower bounds all coordinates of $v$.

Given a rank $n$ matrix $M\in\mathbb Q^{n\times n}$ with non-negative entries and with $M_i\not\leq M_j$ at every $i,j\in\{1,\dots,n\}$ with $i\neq j$ where $M_i$ is $i$th column of $M$ consider the matrix $X$ obtained by $X=(M-\mathsf 1_n)M^{-1}$ ($\mathsf 1_n$ is all $1$s matrix) which is to say if we multiply $X$ with any column of $M$ we get the same column shifted by $1$.

My queries:

1. Are the columns of $M$ the only vectors which have the property that if we multiply $X$ with the vector we get the same vector shifted by $1$?

2. Is there an $i\in\{1,\dots,n\}$ and a vector $v$ at any with $M_i\leq v$ such that $Xv$ is $v$ shifted by $1$?

3. Under what conditions on $M$ can we guarantee $2.$ and can we guarantee $2.$ is violated?

---

The matrices I consider are of type as follows:

$$M[1]=\begin{bmatrix} 0&1&2&3&4&5&6&7\\ 1&0&1&2&3&4&5&6\\ 2&1&0&1&2&3&4&5\\ 3&2&1&0&1&2&3&4\\ 4&3&2&1&0&1&2&3\\ 5&4&3&2&1&0&1&2\\ 6&5&4&3&2&1&0&1\\ 7&6&5&4&3&2&1&0 \end{bmatrix}$$

$$M[2]=\begin{bmatrix} 0&1&2&3&4&5&6&7\\ 1&0&3&2&5&4&7&6\\ 2&3&0&1&6&7&4&5\\ 3&2&1&0&7&6&5&4\\ 4&5&6&7&0&1&2&3\\ 5&4&7&6&1&0&3&2\\ 6&7&4&5&2&3&0&1\\ 7&6&5&4&3&2&1&0\\ \end{bmatrix}$$

Note columns of $M[1]$ are upper bound by columns of $M[2]$.

Answer 1

Assume $n > 1$.

Let $e$ be the $n$-vector with all components equal to $1$, and let $$S=\{v\in\mathbb{R}^n\mid Xv=v-e\}$$

Claim:$\;S$ is closed under affine combinations.

Proof:

Let $u,v\in S$, and suppose $w=(1-t)u+tv$, for some $t\in \mathbb{R}$. \begin{align*} \text{Then}\;\; Xw &=(1-t)Xu+tXv)\\[4pt] &=(1-t)(u-e)+t(v-e)\\[4pt] &=\bigl((1-t)u+tv)\bigr)-\bigl((1-t)e+te\bigr)\\[4pt] &=w-e\\[4pt] \end{align*} which validates the claim.

Since the columns of $M$ are in $S$, and since $M$ is non-singular, it follows that $S$ contains the $(n-1)$-dimensional hyperplane $H$ containing the column vectors of $M$.

Hence, since $0\notin S$, it follows that $S=H$.

Noting that $S$ is infinite, it follows that answer to question $1$ is "no".

For question $2$, I'll assume you meant $M_i < v$ (strict inequality), else the answer would be trivially "yes", simply by taking $v=M_i$.

Assuming that correction, question $2$ asks for conditions on $M$ to determine whether the statement

• For some column $p$ of $M$, there exists $v\in S$ such that $v > p$.

is true or false.

Choose a vector $q$ normal to $H$, such that at least one component of $q$ is positive.

Let $W=\{u-v\mid u,v\in H\}$.

Then $W$ is an $(n-1)$-dimensional subspace of $\mathbb{R}^n$, and $q$ is normal to $W$.

It follows that $W$ contains a strictly positive vector if and only if $q \ge 0$ is false.

Claim:$\;$The answer to question $2$ is "yes" if and only if $q \ge 0$ is false.

Proof:

First suppose $q \ge 0$ is false.

Then $W$ contains a strictly positive vector, $w$ say.

Let $p$ be any column of $M$, and let $v=p+w$.

Then $v\in S$, and $v > p$, so in this case, the answer to question $2$ is "yes".

Next suppose $q \ge 0$.

Then $W$ does not contain a strictly positive vector.

Let $p$ be a column of $M$, and suppose $v > p$, for some $v\in S$.

Then letting $w=v-p$, we get $w\in W$, and $w > 0$, contradiction.

This completes the proof.

Here's an implementation in Maple . . .

Assumptions:

• $M$ is a non-singular $n{\times}n$ matrix, where $n > 1$.$\\[4pt]$
• All entries of $M$are rational.