1
$\begingroup$

Let $A \in \mathbb{Z}^{m \times n}$ be a matrix such that all its column sums are positive: $$\forall j\colon\sum_{i=1}^m A_{ij} \geq 1$$ My question is the following, does there always exists a matrix $C \in \mathbb{Z}^{m \times m}$, $\det(C)\neq 0$, such that all entries of $C\cdot A$ are non negative: $$\forall i, j\colon (C \cdot A)_{ij} \geq 0$$ And if yes, it would be super useful to know how to find it.

Thank you so much in advance for you're input.


Edit: I completely forgot to add an additional restriction on $C$. I think it changes the question quite a bit, but I guess that insights in an answer without this restriction can also help with solving the whole question.

The additional restriction is the following. The columns in $C$ must all add up to the same number $s \in \mathbb{N}$: $$\forall j\colon\sum_{i=1}^m C_{ij} = s$$

Does this make the quest of finding such a $C$ impossible?

Thanks for any further help!

$\endgroup$
5
  • 2
    $\begingroup$ Just an observation, you can think of multiplying by $C$ as a series of Gauss elimination operations. Doing so you can try to construct $CA$ iteratively. Its not trivial, because once you "deal with" once column you can mess with others (and even turn all their elements negative), but this approach suits the problem better in my opnion. $\endgroup$
    – Amit
    Commented Jan 15 at 9:55
  • $\begingroup$ Yes, I also had this reframing in mind already. But I didn't find a way to use this observation effectively. Maybe you do :) $\endgroup$ Commented Jan 15 at 10:00
  • $\begingroup$ One completely different idea I got is to express $C$ in terms of a convex combination of permutation matrices $P_l$. Thus the column sum property automatically follows. We "just" have to make sure that $C\cdot A = \sum_{l=1}^k \lambda_l P_l \cdot A$ has positive entries. Maybe this reframing helps $\endgroup$ Commented Jan 15 at 12:40
  • $\begingroup$ With this reframing you can maybe use the Birkhoff Algorithm. I have no experience with it, I am just stumbling upon that currently ^^ $\endgroup$ Commented Jan 15 at 12:49
  • $\begingroup$ 1/ It almost works with the matrix $C$ filled with $1$s (except it has rank $1$) and 2/ invertibles matrices are dense. $\endgroup$ Commented Jan 16 at 11:29

2 Answers 2

2
$\begingroup$

Remark: This answers an earlier version of the question in which the columns of $C$ were all required to sum to $1$.


No, a matrix $\ C\ $ with the required properties doesn't always exist. Take $$ A=\pmatrix{2&-1\\-1&2}\ , $$ for example. Since the columns of $\ C\ $ must sum to $\ 1\ ,$ it must have the form $$ C=\pmatrix{x&y\\1-x&1-y}\ , $$ where $\ x,y\ $ are integers. You also require the entries of \begin{align} CA&=\pmatrix{x&y\\1-x&1-y}\pmatrix{2&-1\\-1&2}\\ &=\pmatrix{2x-y&-x+2y\\1-2x+y&1+2y-x} \end{align} to be non-negative, which means that \begin{align} 2x-1&\le y\le2x\\ \frac{x}{2}&\le y\le\frac{1+x}{2}\ . \end{align} But the only pairs of integers satisfying this pair of inequalities are $\ x=y=0\ $ and $\ x=y=1\ ,$ and for both of these solutions $\ \det(C)=0\ .$

$\endgroup$
1
  • $\begingroup$ Thank you so much for your input. Yes you are right. I actually just found out that in $C$ all column sums must just be equal and actually not necessarily 1. Sorry for the confusion. In the partial answer I submitted, I made use of that fact. But nontheless, your contribution was super helpful :) $\endgroup$ Commented Jan 15 at 15:23
2
$\begingroup$

First Thoughts

Okay, so here is an idea which seams a little dirty, but is super close to a proper solution. Maybe some of you can complete it. First chose a $C' \in \mathbb{N}^{m \times m}$ such that all entries are $c \in \mathbb{N} \setminus \{0\}$. Thus: $$(C' \cdot A)_{ij} = \sum_{k=1}^m C'_{ik} A_{kj} = c \cdot \sum_{k=1}^m A_{kj} \geq c > 0$$ It seams like we found a good $C = C'$, but $C'$ is not invertable. It is known that there are way more invertible matrices than non-invertable ones. We can use that fact by just adding a random noise matrix $\Delta \in \mathbb{N}^{m \times m}$ onto $C'$. We we hope that the resulting $C := C' + \Delta$ is invertable. If not, we just draw another one and because there are so many more invertable matrices than non-invertable ones, we eventually will draw an invertable $C$.

But we cannot chose $\Delta$ freely. We still have to make sure that the columns of $\Delta$ sum up to the same number - well that is doable. The harder restriction is, that $C\cdot A$ must still only contain positive entries. For that we chose some $\delta \in \mathbb{N}$ and we chose the entries in $\Delta$ such that $\forall i,j\colon 0 \leq \Delta_{ij} \leq \delta$. Let $h \in \mathbb{N}$ be the largest absolute value in $A$. Thus we see that \begin{align*} (C \cdot A)_{ij} &= (\Delta \cdot A)_{ij} + (C' \cdot A)_{ij} \geq \sum_{k=1}^m \Delta_{ik} A_{kj} + c \geq \sum_{k=1}^m -|\Delta_{ik}|\cdot|A_{kj}| + c\\ &\geq \sum_{k=1}^m -\delta h + c = c - mh\delta \end{align*} For that to be non-negative, we just need to select the $\delta$ such that $$0 \leq c - mh\delta \quad\Leftrightarrow\quad \delta \leq \frac{c}{mh}$$ This absolutely no problem, as we can shose $c$ as high as we want and in that way we won't get any negative entries.

This solution is super hand wavy, maybe I get some support from you guys to make this approach more rigorous. So what could one do to make this method more rigorous? Well, I see two ways:

  • Show that this $\Delta$ always exists
  • Construct $\Delta$ deliberately and not by chance.

Edit: Completed Answer

I found an $\Delta$ that will always produce an invertible $C = \Delta + C'$ and makes sure that $C\cdot A$ only contains non-negative entries. It is $\Delta := \delta \cdot I_m$, where $I_m$ is the identity matrix of size $m \times m$ and $\delta \in \mathbb{N} \setminus \{0\}$ (Remember that all entries in $C'$ are all equal to $c \in \mathbb{N}$, just as above). Let's check, that this is exactly what we are looking for.

Is $C$ invertable? Let's take a look at the shape of $C$:

$$C = \begin{pmatrix} c+\delta & c & \cdots & c\\ c & c+\delta & \cdots & c\\ \vdots & \vdots & \ddots & \vdots\\ c & c & \dots & c+\delta \end{pmatrix}$$ It is apparent, that because $\delta \neq 0$ all column vectors are linearly independent. Thus $\Delta$ is indeed invertable.

Does $C \cdot A$ only contain non-negative entries? For that let us chose $\delta$ a little bit more carefully. Let $h \in \mathbb{N}$ be the largest absolut value in $A$: $$h := \max_{i, j} |A_{ij}|$$ Then we will chose $\delta \leq \frac{c}{h}$. This is no problem, as we can chose $c$ as high as we want. Now, let's check what we have to check: \begin{align*} (C \cdot A)_{ij} &= (\delta\cdot I_m\cdot A)_{ij} + (C'\cdot A)_{ij} = \delta \cdot A_{ij} + \sum_{k=1}^m C'_{ik} A_{kj}\\ &= \delta \cdot A_{ij} + c \cdot \underbrace{\sum_{k=1}^m A_{kj}}_{\geq 1} \geq \delta \cdot A_{ij}+ c \geq -\delta\cdot |A_{ij}| + c\\ &\geq -\delta \cdot h + c \geq -\frac{c}{h} \cdot h + c = 0 \end{align*}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .