# The capacity of a finite field matrix channel

Simon R. Blackburn
Department of Mathematics
Royal Holloway University of London
Egham, Surrey TW20 0EX
<EMAIL_ADDRESS>
and
Jessica Claridge
Department of Mathematical Sciences
University of Essex
Wivenhoe Park
Colchester, Essex, CO4 3SQ
<EMAIL_ADDRESS>
###### Abstract

The Additive-Multiplicative Matrix Channel (AMMC) was introduced by Silva,
Kschischang and Kötter in 2010 to model data transmission using random linear
network coding. The input and output of the channel are $n\times m$ matrices
over a finite field $\mathbb{F}_{q}$. On input the matrix $X$, the channel
outputs $Y=A(X+W)$ where $A$ is a uniformly chosen $n\times n$ invertible
matrix over $\mathbb{F}_{q}$ and where $W$ is a uniformly chosen $n\times m$
matrix over $\mathbb{F}_{q}$ of rank $t$.

Silva _et al_ considered the case when $2n\leq m$. They determined the
asymptotic capacity of the AMMC when $t$, $n$ and $m$ are fixed and
$q\rightarrow\infty$. They also determined the leading term of the capacity
when $q$ is fixed, and $t$, $n$ and $m$ grow linearly. We generalise these
results, showing that the condition $2n\geq m$ can be removed. (Our formula
for the capacity falls into two cases, one of which generalises the $2n\geq m$
case.) We also improve the error term in the case when $q$ is fixed.

##  1 Introduction

The _additive-multiplicative matrix channel_ (AMMC) was introduced by Silva,
Kschischang and Kötter [13], and is defined as follows. Let $m$, $n$ and $t$
be positive integers so that $t\leq\min\\{n,m\\}$. The input and output of the
channel are $n\times m$ matrices over a finite field $\mathbb{F}_{q}$. (All
matrices in this paper will have entries in $\mathbb{F}_{q}$.) The AMMC takes
a matrix $X$ as input, and outputs the matrix $Y$ defined by:

$Y=A(X+W),$ (1)

where $A$ and $W$ are chosen uniformly and independently at random, so that
$A$ is an $n\times n$ invertible matrix, and $W$ is an $n\times m$ matrix of
rank $t$.

Silva et al. gave good upper and lower bounds for the capacity of the AMMC
when $2n\leq m$. In particular, when $n$, $m$ and $t$ are fixed with $2n\leq
m$, and when $q\rightarrow\infty$, their paper establishes [13, Corollary 10]
that the capacity tends to $(m-n)(n-t)$ when logarithms are taken to the base
$q$. Moreover, Silva et al. also provide the leading term for the capacity (of
the same form) when $q$ is fixed and $m$, $n$ and $t$ grow linearly.

Our paper aims to generalise these results, by dropping the restriction that
$2n\leq m$. We will show (in both asymptotic regimes considered in [13]) that
the formula for the capacity involves two cases, depending on whether $2n\leq
m+t$ or not. Indeed, we show that the capacity is approximately $(m-n)(n-t)$
when $2n\leq m+t$ (generalising the situation considered by Silva et al.) and
the capacity is approximately $(m-t)^{2}/4$ when $2n>m+t$. See Theorems 11 and
15 below for precise statements. (Note that when $m+t\geq 2n$ we must have
$m\geq 2n-t=n+(n-t)\geq n$, so the formula for the capacity is never
negative!) We mention that the error term in Theorem 15 is a significant
improvement on the corresponding statement in [13]. These results confirm a
conjectured formula for the channel capacity due to Blackburn and Claridge [3,
Section VIII].

Silva et al introduced the AMMC because of an application of the channel to
understanding random linear network coding. We briefly explain this
application; see [2] for more details. In network coding, first defined in by
Ahlswede, Cai, Li and Yeung [1], intermediate nodes of a network are allowed
to compute with and modify packets of data with the aim of increasing the rate
of information flow through the network. For multicast problems, Li, Yeung and
Cai [9] showed that linear network coding (where data packets are regarded as
vectors, and nodes forward linear combinations of the packets they receive) is
sufficient to maximise information flow. Moreover, _random linear network
coding_ (RLNC), where linear combinations are chosen at random, achieves
capacity with probability exponentially approaching $1$ with the code length
[7].

So in RLNC the source injects packets into the network; these packets can be
thought of as vectors of length $m$ with entries in a finite field
$\mathbb{F}_{q}$ (where $q$ is a prime power). The packets flow through a
network of unknown topology to a sink node. Each intermediate node forwards
packets that are random linear combinations of the packets it has received. A
sink node attempts to reconstruct the message from the received packets. See
Figure 1 for an (unrealistically small) example using binary vectors; in
practice $q$ is taken to be large. To relate this example to the AMMC, we see
that the rows of $X$ and $Y$ correspond to the packets transmitted by the
source and received by the sink, respectively. The matrix $A$ corresponds to
the linear combinations of packets computed by the intermediate nodes and the
matrix $W$ corresponds to errors introduced during transmission, and so the
model assumes exactly $t$ linearly independent random errors have been
introduced. In the example of Figure 1, the (rank $3$) input matrix $X$ and
the output matrix $Y$ are

$X=\begin{pmatrix}1&0&0&0&0&0\\\ 0&1&0&0&0&0\\\ 0&0&1&0&0&0\\\ 1&0&1&0&0&0\\\
1&1&0&0&0&0\\\ 1&1&1&0&0&0\\\ \end{pmatrix}\text{ and
}Y=\begin{pmatrix}0&0&0&0&0&0\\\ 0&0&0&0&1&1\\\ 1&0&0&0&0&0\\\ 0&1&0&0&1&1\\\
0&0&0&0&1&1\\\ 0&1&1&0&1&1\\\ \end{pmatrix}.$

Here $Y=A(X+W)$ where

$\displaystyle A$ $\displaystyle=\begin{pmatrix}1&0&1&0&1&0\\\ 0&1&0&0&1&1\\\
1&0&1&1&1&0\\\ 0&0&0&0&1&1\\\ 0&0&1&1&0&1\\\
0&1&0&0&0&1\end{pmatrix}\begin{pmatrix}1&1&0&0&0&0\\\ 0&1&0&0&0&0\\\
0&0&0&1&0&0\\\ 0&0&1&1&0&0\\\ 0&0&0&0&1&0\\\
0&0&0&0&0&1\end{pmatrix}=\begin{pmatrix}1&1&0&1&1&0\\\ 0&1&0&0&1&1\\\
1&1&1&0&1&0\\\ 0&0&0&0&1&1\\\ 0&0&1&0&0&1\\\ 0&1&0&0&0&1\end{pmatrix}\text{
and}$ $\displaystyle W$ $\displaystyle=\begin{pmatrix}1&1&0&0&0&0\\\
0&1&0&0&0&0\\\ 0&0&0&1&0&0\\\ 0&0&1&1&0&0\\\ 0&0&0&0&1&0\\\
0&0&0&0&0&1\end{pmatrix}^{\\!\\!-1}\begin{pmatrix}0&0&0&0&0&0\\\
0&0&0&0&0&0\\\ 0&0&0&0&0&0\\\ 0&0&0&0&0&0\\\ 1&0&1&0&0&0\\\
1&1&0&0&1&1\end{pmatrix}=\begin{pmatrix}0&0&0&0&0&0\\\ 0&0&0&0&0&0\\\
0&0&0&0&0&0\\\ 0&0&0&0&0&0\\\ 1&0&1&0&0&0\\\ 0&1&0&0&1&1\end{pmatrix}.$

$X$$U_{1}$$U_{2}$$U_{3}$$V$$Y$$x_{1}\,x_{2}$$x_{3}\,x_{3}$$x_{5}\,x_{6}$$u_{1}\,u_{2}$$u_{3}\,u_{4}$$u_{5}\,u_{6}$$y_{1}\,y_{2}\,y_{3}\,y_{4}\,y_{5}\,y_{6}$
Figure 1: An example of random network coding. Here we are using binary
vectors of length $6$. Source node $X$ sends (say)
$x_{1}=(100000),x_{2}=(010000),x_{3}=(001000),x_{4}=(101000),x_{5}=(110000)$,
and $x_{6}=(111000)$ to nodes $U_{i}$ as shown.
Nodes $U_{1}$ and $U_{2}$ send linear combinations of received vectors to $V$,
where $u_{1}=x_{1}+x_{2}$, $u_{2}=x_{2}$, $u_{3}=x_{4}$ and
$u_{4}=x_{3}+x_{4}$. The node $U_{3}$ is faulty, and sends random vectors
$u_{5}=x_{5}+(101000)$ and $u_{6}=x_{6}+(110011)$ to $V$.
Finally, node $V$ sends the vectors $y_{i}$ to the sink node $Y$, where
$y_{1}=u_{1}+u_{3}+u_{5}$, $y_{2}=u_{2}+u_{5}+u_{6}$,
$y_{3}=u_{1}+u_{3}+u_{4}+u_{5}$, $y_{4}=u_{5}+u_{6}$,
$y_{5}=u_{3}+u_{4}+u_{6}$ and $y_{6}=u_{2}+u_{6}$.

Our proofs of Theorems 11 and 15 reduce the computation of the AMMC capacity
to finding the capacity of a channel we call the $k$-AMMC, namely the AMMC
with the extra restriction that input matrices are restricted to have rank
$k$. We think that the $k$-AMMC is a natural channel model, of independent
interest.

Alternative finite-field matrix channels, related to the AMMC, have been
proposed to model RLNC. Nóbrega, Silva and Uchôa-Filho [11] considered the
multiplicative matrix channel (MMC)

$Y=AX$

where now $Y$ is a $n\times m$ matrix, $X$ is a $k\times m$ matrix, and the
transfer matrix $A$ is a $n\times k$ matrix chosen according to a distribution
that first picks the rank of $A$ acording to some distribution on ranks, and
then choses $A$ uniformly from all matrices of that rank. Such a distribution
we call Uniform Given Rank (UGR). This channel, along with other MMC variants
with alternative assumptions on the transfer matrix [12], [14], have been used
to model RLNC when no erroneous packets are injected into the network, but
there may be link erasures.

Blackburn and Claridge [3] considered a generalisation of the AMMC, where the
rank of the error matrix $W$ varies, allowing the modelling of different error
patterns; Silva et al. [13] also discuss such channels. Nóbrega, Silva and
Uchôa-Filho [11], and Blackburn and Claridge [3] both show that for the
channels they consider, there always exists a UGR input distribution that
achieves capacity. This reduces the problem of finding capacity achieving
input distributions to finding a ‘good’ distribution on ranks. This aligns
with our approach here, reducing the computation of the AMMC capacity to
finding the capacity of the $k$-AMMC, and indeed we show in Lemma 6 that a
capacity achieving input distribution of the $k$-AMMC can be taken to be
uniform.

Finally, we mention that Nóbrega, Feng, Silva and Uchôa-Filho [10] and Feng,
Nóbrega, Kschischang and Silva [6], considered the MMC and AMMC, respectively,
over finite chain rings, thus moving away from the finite-field case.

The structure of the paper is as follows. In Section 2 we present an overview
of our approach, giving intuition behind the expected capacity formula. In
Section 3 we prove some combinatorial bounds from linear algebra that we need.
In Section 4 we establish the capacity of the $k$-AMMC when
$q\rightarrow\infty$ with other parameters fixed. In Section 5 we use the
results from Section 4 to establish the capacity of the AMMC in this
asymptotic regime. In Section 6, we show how the results in Sections 4 and 5
may be modified to provide the leading term of the capacity when $q$ is fixed
and when $n$, $m$ and $t$ grow linearly. Finally, Section 7 describes a coding
scheme for the channel which achieves capacity in both the asymptotic regimes
considered.

### Acknowledgement

The authors would like to thank the London Mathematical Society, who funded
their collaboration via a Scheme 4 Grant reference 42124.

##  2 Overview

We give an intuitive justification for the AMMC capacity, as a guide to the
proofs in the sections which follow.

We first consider the $k$-AMMC, so the input to the channel is constrained to
matrices of rank $k$. We will show that the capacity achieving input
distribution is uniform on such matrices. Note that multiplying by $A$
replaces the matrix $X+W$ with a random matrix having the same row space.
Moreover, we can show that the output distribution of the AMMC only depends on
the row space of $X$, $\mathrm{row}(X)$, rather than $X$ itself. So the
channel can be thought of as having row spaces (of $X$ and $X+W$ respectively)
as input and output: the receiver is given
$\mathrm{row}(Y)=\mathrm{row}(X+W)$, and must deduce information about
$\mathrm{row}(X)$ from this.

Now $\mathrm{row}(Y)\subseteq\mathrm{row}(X)+\mathrm{row}(W)$. We would expect
$\mathrm{row}(X)$ and $\mathrm{row}(W)$ to have no special relationship to
each other (as $\mathrm{row}(W)$ is uniformly and independently chosen of
dimension $t$), so we expect the dimension of
$\mathrm{row}(X)+\mathrm{row}(W)$ to be close to $\min\\{m,k+t\\}$. Hence
$\mathrm{rk}(Y)=\dim(\mathrm{row}(Y))\leq\min\\{m,k+t\\}$. Since
$\mathrm{row}(Y)$ is the row space of an $n\times m$ matrix, we must have
$\mathrm{rk}(Y)\leq\min\\{n,m\\}$. We show that $\mathrm{rk}(Y)$ is usually
close to being as large as possible given these constraints. So we show that
with high probability,

$\mathrm{rk}(Y)\approx\min\\{m,n,k+t\\}=\min\\{n,k+t-\delta\\},$

where $\delta=\max\\{0,k+t-m\\}$. We will also determine the approximate
dimension of $\mathrm{row}(X)\cap\mathrm{row}(Y)$:

$\dim(\mathrm{row}(X)\cap\mathrm{row}(Y))\approx\min\\{k,n-(t-\delta)\\}$

with high probability. The proof that $\mathrm{rk}(Y)$ and
$\dim(\mathrm{row}(X)\cap\mathrm{row}(Y))$ can be approximately determined
(see Lemmas 9 and 13) is the most difficult part of the argument.

The receiver initially knows nothing of $\mathrm{row}(X)$, so the entropy of
$\mathrm{row}(X)$ is equal to the logarithm to the base $q$ of the number of
dimension $k$ subspaces of $\mathbb{F}_{q}^{m}$. Once the receiver obtains
$Y$, the entropy of $\mathrm{row}(X)$ is reduced, as $\mathrm{row}(X)$ is
likely to have an intersection of dimension approximately
$\min\\{k,n-(t-\delta)\\}$ with the (known) subspace $\mathrm{row}(Y)$ of
dimension approximately $\min\\{n,k+t-\delta\\}$. Counting these subspaces
allows us to determine the capacity of the $k$-AMMC, by taking logarithms to
the base $q$.

We then show that the capacity of the AMMC is essentially the maximum of the
capacities of the $k$-AMMC as $k$ varies (because there are few possibilities
for $k$). When $k$ is large (more precisely, when $k+t>\min\\{n,m\\}$) the
receiver does not obtain much information about $\mathrm{row}(X)$, as this
subspace does not normally intersect $\mathrm{row}(Y)$ in a space of large
dimension. We show that it is never advantageous to choose a large value of
$k$. When $k+t\leq\min\\{m,n\\}$, we have that $\mathrm{rk}(X+W)=k+t$ with
non-trivial probability, and
$\mathrm{row}(Y)=\mathrm{row}(X+W)=\mathrm{row}(X)+\mathrm{row}(W)$. Thus the
receiver is given a subspace $\mathrm{row}(Y)$ of dimension $k+t$, and knows
that $\mathrm{row}(X)$ lies in this subspace. Our formula for the capacity of
the channel is approximately $(m-t-k)k$ in this case. The maximum value of
this formula is at $k=(m-t)/2$, which always lies in the range $0\leq k\leq
m-t$. So the best value for $k$ depends on whether $(m-t)/2\leq n-t$ (when we
take $k\approx(m-t)/2$) or $(m-t)/2>n-t$ (when we take $k=n-t$). This is why
the formula for the capacity of the AMMC splits into two cases.

##  3 Preliminaries from linear algebra

This section contains various counting results from linear algebra, which we
will use in the following sections.

######  Lemma 1.

Let $a$ be a fixed non-negative integer. Suppose $x_{1},x_{2},\ldots,x_{a}$
are vectors picked uniformly and independently from a vector space over
$\mathbb{F}_{q}$ of dimension $a$. Then

$\mathrm{P}\big{(}\dim\langle
x_{1},x_{2},\ldots,x_{a}\rangle=a\big{)}=\prod_{j=1}^{a}(1-q^{-j})>\frac{1}{4}.$
(2)

Moreover when $q\rightarrow\infty$ with $a$ fixed,

$\mathrm{P}\big{(}\dim\langle
x_{1},x_{2},\ldots,x_{a}\rangle=a\big{)}\rightarrow 1.$ (3)

###### Proof.

There are $q^{a^{2}}$ choices for the vectors $x_{1},x_{2},\ldots x_{a}$.
These vectors span an $a$-dimensional space if and only if they are linearly
independent, and so the number of choices for linearly independent vectors
$x_{1},x_{2},\ldots,x_{a}$ is $\prod_{i=0}^{a-1}(q^{a}-q^{i})$. Therefore

$\displaystyle\mathrm{P}\big{(}\dim\langle
x_{1},x_{2},\ldots,x_{a}\rangle=a\big{)}$
$\displaystyle=\frac{1}{q^{a^{2}}}\left(\prod_{i=0}^{a-1}(q^{a}-q^{i})\right)$
$\displaystyle=\prod_{i=0}^{a-1}(1-q^{i-a})$
$\displaystyle=\prod_{j=1}^{a}(1-q^{-j}).$

Each factor in this product tends to $1$ as $q\rightarrow\infty$, hence (3)
follows. It remains to show $\prod_{j=1}^{a}(1-q^{-j})>1/4$. To see this:

$\displaystyle\prod_{j=1}^{a}(1-q^{-j})$
$\displaystyle>\prod_{j=1}^{\infty}(1-q^{-j})$
$\displaystyle\geq\prod_{j=1}^{\infty}(1-2^{-j})$
$\displaystyle=\sum_{i=1}^{\infty}(-1)^{i}(2^{-i(3i+1)/2}+2^{-i(3i-1)/2})$ (by
Euler’s pentagonal number theorem) $\displaystyle\geq
1-(1/2)-(1/4)+(1/2^{5})+(1/2^{7})-(1/2^{12})\sum_{i=0}^{\infty}2^{-i}$
$\displaystyle=(1/4)+(1/2^{5})+(1/2^{7})-(1/2^{11})$ $\displaystyle>1/4.\qed$

The Gaussian binomial coefficient, or _$q$ -binomial coefficient_, is written
$\genfrac{[}{]}{0.0pt}{}{\,a\,}{b}_{q}$ and defined to be the number of
$b$-dimensional subspaces of an $a$-dimensional space over $\mathbb{F}_{q}$. A
formula for the Gaussian binomial coefficient is (see, for example, Cameron
[4, §9.2])

$\genfrac{[}{]}{0.0pt}{}{\,a\,}{b}_{q}=\left\\{\begin{array}[]{ll}\prod_{i=0}^{b-1}\frac{(q^{a}-q^{i})}{(q^{b}-q^{i})}&\text{for
}b\leq a,\\\ 0&\text{for }b>a.\end{array}\right.$

######  Lemma 2.

Let $a$ and $b$ be non-negative integers, with $b\leq a$. Then

$q^{(a-b)b}<\genfrac{[}{]}{0.0pt}{}{\,a\,}{b}_{q}\leq f(q)\,q^{(a-b)b}\leq
q^{(a-b)b+\log_{q}4},$ (4)

where $f(q)$ is a function of $q$ such that $1\leq f(q)\leq 4$ for all
integers $q$. When $q\rightarrow\infty$ with $a$ and $b$ fixed,

$\genfrac{[}{]}{0.0pt}{}{\,a\,}{b}_{q}\,/\,q^{(a-b)b}\rightarrow 1.$ (5)

In particular, when $q\rightarrow\infty$ with $a$ and $b$ fixed,

$\log_{q}\genfrac{[}{]}{0.0pt}{}{\,a\,}{b}_{q}\rightarrow(a-b)b.$ (6)

###### Proof.

The inequalities (4) are provided by Kötter and Kschischang [8, Lemma 4]).
Here is a direct proof. Writing

$\genfrac{[}{]}{0.0pt}{}{\,a\,}{b}_{q}=q^{(a-b)b}\prod_{i=0}^{b-1}\left(\frac{1-q^{-a+i}}{1-q^{-b+i}}\right),$

we note that

$\displaystyle 1$
$\displaystyle<\prod_{i=0}^{b-1}\left(\frac{1-q^{-a+i}}{1-q^{-b+i}}\right)$
$\displaystyle<\prod_{i=0}^{b-1}\left(\frac{1}{1-q^{-b+i}}\right)$
$\displaystyle=\frac{1}{\prod_{j=1}^{b}(1-q^{-j})}.$

The expressions (4) and (5) follow, as
$f(q)=\frac{1}{\prod_{j=1}^{b}(1-q^{-j})}<4$, and $f(q)\rightarrow 1$ as
$q\rightarrow\infty$, by Lemma 1. The limit (6) follows since
$\log_{q}4\rightarrow 0$ as $q\rightarrow\infty$. ∎

######  Corollary 3.

Let $n$, $m$, $k$ and $t$ be fixed non-negative integers, with
$t\leq\min\\{n,m\\}$ and $k\leq\min\\{n,m\\}$.

  * (a)

When $k+t\leq m$,

$\genfrac{[}{]}{0.0pt}{}{\,m-k\,}{t}_{q}q^{tk}/\genfrac{[}{]}{0.0pt}{}{\,m\,}{t}_{q}\rightarrow
1\text{ as }q\rightarrow\infty.$

  * (b)

When $k+t\geq m$,

$\genfrac{[}{]}{0.0pt}{}{\,k\,}{k+t-m}_{q}q^{(m-k)(m-t)}/\genfrac{[}{]}{0.0pt}{}{\,m\,}{t}_{q}\rightarrow
1\text{ as }q\rightarrow\infty.$

###### Proof.

To prove (a), we note that
$\genfrac{[}{]}{0.0pt}{}{\,m-k\,}{t}_{q}q^{tk}/\genfrac{[}{]}{0.0pt}{}{\,m\,}{t}_{q}$
may be written as

$\left(\frac{\genfrac{[}{]}{0.0pt}{}{\,m-k\,}{t}_{q}}{q^{t(m-k-t)}}\right)\left(\frac{q^{t(m-t)}}{\genfrac{[}{]}{0.0pt}{}{\,m\,}{t}_{q}}\right).$

Both of the factors in the expression above tend to $1$ by (5), so (a)
follows.

Similarly, we may prove (b) by writing
$\genfrac{[}{]}{0.0pt}{}{\,k\,}{k+t-m}_{q}q^{(m-k)(m-t)}/\genfrac{[}{]}{0.0pt}{}{\,m\,}{t}_{q}$
as

$\left(\frac{\genfrac{[}{]}{0.0pt}{}{\,k\,}{k+t-m}_{q}}{q^{(k+t-m)(m-t)}}\right)\left(\frac{q^{t(m-t)}}{\genfrac{[}{]}{0.0pt}{}{\,m\,}{t}_{q}}\right).\qed$

######  Lemma 4.

Let $a$ and $b$ be fixed non-negative integers, and let $U$ be a space of
dimension $a$ over $\mathbb{F}_{q}$. When $x_{1},x_{2},\ldots,x_{b}\in U$ are
uniformly and independently chosen,

$\mathrm{P}\big{(}\dim\langle
x_{1},x_{2},\ldots,x_{b}\rangle=\min\\{a,b\\}\big{)}\rightarrow 1\text{ as
}q\rightarrow\infty.$

###### Proof.

Write $\ell=\min\\{a,b\\}$. The probability we are interested in is bounded
below by the probability that $x_{1},x_{2},\ldots,x_{\ell}$ are linearly
independent. So

$\displaystyle\mathrm{P}\big{(}\dim\langle
x_{1},x_{2},\ldots,x_{b}\rangle=\min\\{a,b\\}\big{)}$
$\displaystyle\geq\mathrm{P}\big{(}\dim\langle
x_{1},x_{2},\ldots,x_{\ell}\rangle=\ell\big{)}$
$\displaystyle=\frac{1}{q^{a\ell}}\left(\prod_{i=0}^{\ell-1}(q^{a}-q^{i})\right)$
$\displaystyle=\prod_{i=0}^{\ell-1}(1-q^{i-a})$
$\displaystyle\geq\prod_{i=0}^{\ell-1}(1-q^{i-\ell}).$

This last expression tends to $1$ by Lemma 1, so the lemma follows. ∎

######  Lemma 5.

Let $n$, $m$ and $k$ be fixed non-negative integers such that
$k\leq\min\\{n,m\\}$. Let $\rho(n,m,k)$ be the number of $n\times m$ matrices
over $\mathbb{F}_{q}$ of rank $k$. Then

$\log_{q}\rho(n,m,k)\rightarrow(n+m-k)k\text{ as }q\rightarrow\infty.$

###### Proof.

There are $\genfrac{[}{]}{0.0pt}{}{\,m\,}{k}_{q}$ possibilities for the row
space $U$ of a matrix counted by $\rho(n,m,k)$. Suppose $U$ is fixed: we wish
to count the number of $n\times m$ matrices $M$ with row space $U$. Writing
$x_{i}$ for the $i$th row of $M$, we are asking for the number of choices for
$x_{1},x_{2},\ldots,x_{n}\in U$ such that $\langle
x_{1},x_{2},\ldots,x_{n}\rangle=U$. Since $|U|=q^{k}$, the number of choices
is $\pi\cdot q^{nk}$ where $\pi$ is the probability that uniformly and
independently chosen vectors $x_{1},x_{2},\ldots,x_{n}\in U$ are such that
$\langle x_{1},x_{2},\ldots,x_{n}\rangle=U$. Lemma 4 implies that
$\pi\rightarrow 1$ as $q\rightarrow\infty$. So

$\displaystyle\log_{q}\rho(n,m,k)$
$\displaystyle=\log_{q}\left(\genfrac{[}{]}{0.0pt}{}{\,m\,}{k}_{q}\right)\pi
q^{kn}$
$\displaystyle=\log_{q}\left(\genfrac{[}{]}{0.0pt}{}{\,m\,}{k}_{q}\right)+\log_{q}\pi+nk$
$\displaystyle\rightarrow(m-k)k+0+nk\text{ by~{}\eqref{eqn:log_qbinomial}}$
$\displaystyle=(n+m-k)k,$

as required. ∎

##  4 The $k$-dimensional AMMC

For a fixed non-negative integer $k$ such that $k\leq\min\\{n,m\\}$ we define
the _rank $k$ input additive-multiplicative matrix channel,_ and write
$k$-AMMC, to be the AMMC channel with input matrices $X$ restricted to having
rank $k$. This section determines the asymptotic capacity of this channel when
$q\rightarrow\infty$ with $n,m,t$ and $k$ fixed.

######  Lemma 6.

The capacity of the $k$-AMMC is achieved when the input distribution
$\mathbf{X}$ is uniform over all $n\times m$ matrices $X$ of rank $k$.

###### Proof.

The lemma is a special case of [3, Theorem 1]. We may prove the lemma directly
in this case as follows.

Let $X$ and $X^{\prime}$ be $n\times m$ matrices of rank $k$. Since we can
row- and column-reduce each of $X$ and $X^{\prime}$ to the same matrix

$\begin{pmatrix}I_{k}&0_{k\times(m-k)}\\\ 0_{(n-k)\times
k}&0_{(n-k)\times(m-k)}\end{pmatrix}$

there exists an invertible $n\times n$ matrix $N$ and an invertible $m\times
m$ matrix $M$ so that $NXM=X^{\prime}$. Then $A(X+W)=Y$ if and only if
$NA(XM+WM)=NYM$, which holds if and only if $NAN^{-1}(X^{\prime}+NWM)=NYM$.
The matrix $NWM$ is uniform of rank $t$ when $W$ is chosen uniformly of rank
$t$, and the matrix $NAN^{-1}$ is uniform over invertible $n\times n$ matrices
when the same is true for $A$. So for any input distribution $\mathbf{X}$ with
corresponding output distribution $\mathbf{Y}$,

$\mathrm{P}(\mathbf{Y}=Y|\mathbf{X}=X)=\mathrm{P}(\mathbf{Y}=NYM|\mathbf{X}=X^{\prime}).$

The map $\phi$ taking an $n\times m$ matrix $Y$ to the $n\times m$ matrix
$\phi(Y)=NYM$ is a permutation of output matrices. Hence
$H(\mathbf{Y}|\mathbf{X}=X)=H(\mathbf{Y}|\mathbf{X}=X^{\prime})$ for any rank
$k$ matrices $X$ and $X^{\prime}$. Let $h$ be this common value of the
entropy. Let $\mathbf{X}$ be an input distribution, and let $\mathbf{Y}$ be
the corresponding output distribution. Then

$H(\mathbf{Y}|\mathbf{X})=\sum_{X}\mathrm{P}(\mathbf{X}=X)H(\mathbf{Y}|\mathbf{X}=X)=\sum_{X}\mathrm{P}(\mathbf{X}=X)\cdot
h=h.$

Hence
$I(\mathbf{X};\mathbf{Y})=H(\mathbf{Y})-H(\mathbf{Y}|\mathbf{X})=H(\mathbf{Y})-h$.
So a capacity achieving input distribution is one in which $H(\mathbf{Y})$ is
maximised.

Note that the permutation above does not change the rank of the output matrix.
Hence the probability $p_{r}$ that the output of the $k$-AMMC has rank $r$
given that a matrix $X$ is input does not depend on the matrix $X$, just the
parameters $k$, $t$, $m$, $n$ and $q$. So an output distribution $\mathbf{Y}$
has the property that $\mathrm{P}(\mathrm{rk}(\mathbf{Y})=r)=p_{r}$, whatever
the input distribution $\mathbf{X}$. Hence $H(\mathbf{Y})$ is bounded above by
entropy of the distribution that is obtained by choosing the rank $r$ of a
matrix $r$ with probability $p_{r}$, and then choosing $Y$ uniformly of rank
$r$. But this distribution is attained by choosing an input distribution
$\mathbf{X}$ that is uniform of rank $k$. So the lemma follows. ∎

######  Lemma 7.

Let $n$, $m$, $k$ and $t$ be fixed non-negative integers, with
$k\leq\min\\{n,m\\}$ and $t\leq\min\\{m,n\\}$. Consider the $k$-AMMC with
uniform input distribution $\mathbf{X}$ and corresponding output distribution
$\mathbf{Y}$. For matrices $X$ and $Y$, the probability
$\mathrm{P}(\mathbf{X}=X|\mathbf{Y}=Y)$ depends only on
$\dim(\mathrm{row}(X)\cap\mathrm{row}(Y))$ and $\mathrm{rk}(Y)$.

###### Proof.

Let $Y$ and $Y^{\prime}$ be fixed $n\times m$ matrices of rank $r$. For an
$n\times m$ matrix $X$, define $\Omega(X)$ to be the set of pairs $(W,A)$
where $W$ is an $n\times m$ matrix of rank $t$, $A$ is an invertible $n\times
n$ matrix, and $Y=A(X+W)$. Note that, since $\mathbf{X}$ is uniform,
$\mathrm{P}(\mathbf{X}=X|\mathbf{Y}=Y)$ is proportional to $|\Omega(X)|$.
Similarly, for an $n\times m$ matrix $X^{\prime}$, define
$\Omega^{\prime}(X^{\prime})$ to be the set of pairs $(W,A)$ where $W$ is an
$n\times m$ matrix of rank $t$, $A$ is an invertible $n\times n$ matrix, and
$Y^{\prime}=A(X^{\prime}+W)$. Again,
$\mathrm{P}(\mathbf{X}=X^{\prime}|\mathbf{Y}=Y^{\prime})$ is proportional to
$|\Omega^{\prime}(X^{\prime})|$.

Let $s$ be a positive integer, and let $X$ and $X^{\prime}$ be two $n\times m$
matrices of rank $k$ such that

$\dim(\mathrm{row}(X)\cap\mathrm{row}(Y))=\dim(\mathrm{row}(X^{\prime})\cap\mathrm{row}(Y^{\prime}))=s.$

The lemma follows if we can show that

$\mathrm{P}(\mathbf{X}=X|\mathbf{Y}=Y)=\mathrm{P}(\mathbf{X}=X^{\prime}|\mathbf{Y}=Y^{\prime}).$

It suffices to show that $|\Omega(X)|=|\Omega^{\prime}(X^{\prime})|$. Choose a
basis $y_{1},y_{2},\ldots,y_{r}$ for $\mathrm{row}(Y)$ such that
$y_{1},y_{2},\ldots,y_{s}$ is a basis for
$\mathrm{row}(Y)\cap\mathrm{row}(X)$. Extend this basis to a basis
$y_{1},y_{2},\ldots,y_{r},x_{1},x_{2},\ldots x_{m-r}$ for $\mathbb{F}_{q}^{m}$
in such a way that $y_{1},y_{2},\ldots,y_{s},x_{1},x_{2},\ldots,x_{k-s}$ is a
basis for $\mathrm{row}(X)$. Construct a similar basis
$y^{\prime}_{1},y^{\prime}_{2},\ldots,y^{\prime}_{r},x^{\prime}_{1},x^{\prime}_{2},\ldots
x^{\prime}_{m-r}$ corresponding to $X^{\prime}$ and $Y^{\prime}$. So the
vectors $y^{\prime}_{1},\ldots,y^{\prime}_{s}$ form a basis for
$\mathrm{row}(Y^{\prime})\cap\mathrm{row}(X^{\prime})$, the vectors
$y^{\prime}_{1},y^{\prime}_{2},\ldots,y^{\prime}_{r}$ form a basis for
$\mathrm{row}(Y^{\prime})$, and the vectors
$y^{\prime}_{1},y^{\prime}_{2},\ldots,y^{\prime}_{s},x^{\prime}_{1},x^{\prime}_{2},\ldots,x^{\prime}_{k-s}$
form a basis for $\mathrm{row}(X^{\prime})$. Let $M$ be the unique
(invertible) $m\times m$ matrix such that $y_{i}M=y^{\prime}_{i}$ and
$x_{i}M=x^{\prime}_{i}$. Note that right-multiplication by $M$ maps
$\mathrm{row}(Y)$ to $\mathrm{row}(Y^{\prime})$ and maps $\mathrm{row}(X)$ to
$\mathrm{row}(X^{\prime})$. Hence $\mathrm{row}(YM)=\mathrm{row}(Y^{\prime})$
and $\mathrm{row}(XM)=\mathrm{row}(X^{\prime})$. Since $XM$ and $X^{\prime}$
have the same row space, there exists an invertible $n\times n$ matrix $N$
such that $NXM=X^{\prime}$. Since
$\mathrm{row}(Y^{\prime})=\mathrm{row}(YM)=\mathrm{row}(NYM)$, there exists an
invertible $n\times n$ matrix $K$ such that $K(NYM)=Y^{\prime}$. Define a map
$\phi:\Omega(X)\rightarrow\Omega(X^{\prime})$ by
$\phi((W,A))=(NWM,KNAN^{-1})$. The map is well defined bijection since the
following equations are equivalent for matrices $A$ and $W$:

$\displaystyle A(X+W)=Y$ $\displaystyle KNA(X+W)M=KNYM$ $\displaystyle
KNAN^{-1}(NXM+NWM)=Y^{\prime}$ $\displaystyle
KNAN^{-1}(X^{\prime}+NWM)=Y^{\prime}$

So the lemma follows. ∎

######  Lemma 8.

Let $n$, $m$, $k$ and $t$ be fixed non-negative integers, with
$k\leq\min\\{n,m\\}$ and $t\leq\min\\{m,n\\}$. Let $U$ and $V$ be sampled
uniformly and independently at random from the set of all subspaces of
$\mathbb{F}_{q}^{m}$ of dimension $k$ and dimension $t$ respectively. Define
$\delta=\max\\{0,k+t-m\\}$. Then $\dim(U\cap V)=\delta$ with probability
tending to $1$ as $q\rightarrow\infty$.

###### Proof.

Suppose first that $k+t\leq m$, and so $\delta=0$. For any fixed subspace $U$,
the proportion of subspaces $V$ that intersect $U$ trivially is

$\genfrac{[}{]}{0.0pt}{}{\,m-k\,}{t}_{q}q^{tk}\,/\,\genfrac{[}{]}{0.0pt}{}{\,m\,}{t}_{q},$

which tends to $1$ as $q\rightarrow\infty$, by Corollary 3. So the lemma
follows in this case.

Now suppose $k+t\geq m$, and so $\delta=k+t-m$. Note that $\dim(U\cap
V)=\delta$ if and only if

$\dim(U+V)=\dim(U)+\dim(V)-\dim(U\cap V)=k+t-(k+t-m)=m.$

For any fixed subspace $U$, the proportion of subspaces $V$ that intersect $U$
in a subspace of dimension $k+t-m$ is

$\genfrac{[}{]}{0.0pt}{}{\,k\,}{k+t-m}_{q}q^{(m-k)(k-(k+t-m)}\,/\,\genfrac{[}{]}{0.0pt}{}{\,m\,}{t}_{q},$

which tends to $1$ as $q\rightarrow\infty$, by Corollary 3. So the lemma
follows. ∎

######  Lemma 9.

Let $n$, $m$, $k$ and $t$ be fixed non-negative integers, with
$k\leq\min\\{n,m\\}$ and $t\leq\min\\{m,n\\}$. Define
$\delta=\max\\{0,k+t-m\\}$. Let $X$ and $W$ be $n\times m$ matrices, chosen
uniformly and independently at random subject to $\mathrm{rk}(X)=k$ and
$\mathrm{rk}(W)=t$. Let $Y=A(X+W)$, where $A$ is chosen uniformly at random
from all $n\times n$ invertible matrices. Then with probability at least $p$,
where $p\rightarrow 1$ as $q\rightarrow\infty$, we have

$\displaystyle\mathrm{rk}(Y)=\min\\{t+k,m,n\\},\text{ and }$ (7)
$\displaystyle\dim(\mathrm{row}(X)\cap\mathrm{row}(Y))=\min\\{k,n-(t-\delta)\\}.$
(8)

###### Proof.

We note that the conditions (7) and (8) depend only on $\mathrm{row}(Y)$.
Since left-multiplication by an invertible matrix does not change the row
space we may assume, without loss of generality, that $A$ is the identity
matrix and so $Y=X+W$. So the $i$th row $y_{i}$ of $Y$ has the form
$y_{i}=x_{i}+w_{i}$, where $x_{i}\in\mathbb{F}^{m}$ and
$w_{i}\in\mathbb{F}^{m}$ are the $i$th rows of $X$ and $W$ respectively.

Choose subspaces $U$ and $V$ of $\mathbb{F}_{q}^{m}$ of dimensions $k$ and $t$
uniformly and independently at random. By Lemma 8, $\dim(U\cap V)=\delta$ with
probability $p_{0}$, where $p_{0}\rightarrow 1$ as $q\rightarrow\infty$. So to
prove the lemma, it suffices to fix $U$ and $V$ such that $\dim(U\cap
V)=\delta$, and then select $X$ and $W$ uniformly at random subject to
$\mathrm{row}(X)=U$ and $\mathrm{row}(W)=V$: If we can show that the
conditions (7) and (8) hold with probability at least $p_{1}$ where
$p_{1}\rightarrow 1$ as $q\rightarrow\infty$, then the lemma holds with
$p=p_{0}p_{1}$.

Fix subspaces $U$ and $V$ of $\mathbb{F}_{q}^{m}$ such that $\dim(U)=k$,
$\dim(V)=t$ respectively and $\dim(U\cap V)=\delta$. We generate two $n\times
m$ matrices $X$ and $W$ by the following random process. We choose vectors
$x_{1},x_{2},\ldots,x_{n}\in U$ and vectors $w_{1},w_{2},\ldots,w_{n}\in V$
uniformly and independently at random. We set $X$ to be the matrix whose $i$th
row is $x_{i}$, and we set $W$ to be the matrix whose $i$th row is $w_{i}$.
Let $Y=X+W$, the matrix whose $i$th row is $x_{i}+w_{i}$. Now
$\mathrm{row}(X)\subseteq U$ with equality if and only if the vectors $x_{i}$
span $U$: this happens with probability at least

$\prod_{j=1}^{k}(1-q^{-j}),$

since, by Lemma 1, this expression is the probability that the first $k$ rows
of $X$ span $U$. Similarly, the probability that $\mathrm{row}(W)=V$ is at
least

$\prod_{j=1}^{t}(1-q^{-j}).$

Let $\mathbf{E}$ be the indicator variable for the event that
$\mathrm{row}(X)=U$ and $\mathrm{row}(W)=V$. Since the event that
$\mathrm{row}(X)=U$ and the event that $\mathrm{row}(W)=V$ are independent, we
see that

$\mathrm{P}(\mathbf{E}=1)\geq\prod_{j=1}^{k}(1-q^{-j})\cdot\prod_{j=1}^{t}(1-q^{-j})\rightarrow
1$

as $q\rightarrow\infty$.

When $\mathbf{E}=1$, the matrices $X$ and $W$ are uniformly and independently
chosen such that $\mathrm{row}(X)=U$ and $\mathrm{row}(W)=V$. So we are
interested in the probability that the conditions (7) and (8) hold conditional
on $\mathbf{E}=1$. However, we begin by considering the unconditional
probability.

The quotient space $(U+V)/U$ has dimension $t-\delta$, since $(U+V)/U\cong
V/V\cap U$. The image of the $i$th row $y_{i}$ of $Y$ in $(U+V)/U$ is
$y_{i}+U=x_{i}+w_{i}+U=w_{i}+U$. Since $w_{1},w_{2},\ldots,w_{t-\delta}$ are
chosen uniformly and independently from $V$, the first $t-\delta$ rows of $Y$
span $U+V$ modulo $U$ with probability

$\prod_{j=1}^{t-\delta}(1-q^{-j})\rightarrow 1\text{ as }q\rightarrow\infty,$

by Lemma 1. When the first $t-\delta$ rows of $Y$ span $U+V$ modulo $U$, there
exist field elements $\alpha_{u,j}\in\mathbb{F}_{q}$ with $t-\delta<u\leq n$
and $1\leq j\leq t-\delta$ such that

$w_{u}=\sum_{j=1}^{t-\delta}\alpha_{u,j}w_{j}\bmod U.$

Consider the $n-(t-\delta)$ vectors
$z_{(t-\delta)+1},z_{(t-\delta)+2},\ldots,z_{n}$ in $\mathrm{row}(Y)$ defined
by

$\displaystyle z_{u}$
$\displaystyle=y_{u}-\sum_{j=1}^{t-\delta}\alpha_{u,j}y_{j}$
$\displaystyle=x_{u}-\left(\sum_{j=1}^{t-\delta}\alpha_{u,j}x_{j}\right)+\left(w_{u}-\sum_{j=1}^{t-\delta}\alpha_{u,j}w_{j}\right).$
(9)

The last term in (9) lies in $U$, by our choice of the elements
$\alpha_{i,j}$. The remaining terms lie in $U$ since $x_{i}\in U$. Hence
$z_{u}\in U\cap\mathrm{row}(Y)$. Moreover, the vectors $z_{u}$ are uniformly
and independently chosen from $U$, since the vectors $x_{u}$ for
$t-\delta<u\leq n$ are only involved in the sum (9) for one value of $u$. So,
by Lemma 4, with probability tending to $1$ we have a set of $n-(t-\delta)$
vectors in $\mathrm{row}(Y)$ which span a subspace of $U$ of dimension
$\min\\{k,n-(t-\delta)\\}$. Thus
$\dim(\mathrm{row}(X)\cap\mathrm{row}(Y))\geq\min\\{k,n-(t-\delta)\\}$ with
probability tending to $1$. Clearly
$\dim(\mathrm{row}(X)\cap\mathrm{row}(Y))\leq\dim(\mathrm{row}(X))\leq k$.
Since we are assuming the first $t-\delta$ rows of $Y$ span a subspace of
dimension $t-\delta$ modulo $U$, and since the row space of $Y$ is spanned by
$n$ vectors, we see that $\dim(\mathrm{row}(Y)\cap U)\leq n-(t-\delta)$. Hence
with probability tending to $1$ our random process produces matrices $X$, $W$
and $Y$ such that (8) holds.

We now check that our random process produces a matrix $Y$ such that (7) holds
with probability tending to $1$. Since $Y$ is an $n\times m$ matrix,
$\mathrm{rk}(Y)\leq\min\\{n,m\\}$. Since
$\mathrm{row}(Y)\subseteq\mathrm{row}(U)+\mathrm{row}(V)$ which is a space of
dimension at most $t+k$, we see that $\mathrm{rk}(Y)\leq t+k$ and so
$\mathrm{rk}(Y)\leq\min\\{t+k,m,n\\}$. The argument in the previous paragraph
shows that with probability tending to $1$ the row space of $Y$ contains a
linearly independent set of size
$t-\delta+\min\\{k,n-(t-\delta)\\}=\min\\{t+k-\delta,n\\}$. When $t+k\leq m$
we have $\delta=0$ and so
$\mathrm{rk}(Y)\geq\min\\{t+k,n\\}=\min\\{t+k,n,m\\}$. When $t+k>m$ then
$\delta=m-(t+k)$ and so $\mathrm{rk}(Y)\geq\min\\{m,n\\}=\min\\{t+k,n,m\\}$.
So in either case the equation (7) holds with probability tending to $1$.

We have shown that our random process produces matrices $X$, $W$ and $Y$ such
that (7) and (8) hold with probabilities tending to $1$, and we have shown
that $\mathrm{P}(\mathbf{E}=1)=p_{2}$ where $p_{2}\rightarrow 1$ as
$q\rightarrow\infty$. So (7), (8) and $\mathbf{E}=1$ simutaneously hold with
probability $p_{3}$ where $p_{3}\rightarrow 1$ as $q\rightarrow\infty$. Hence

$\displaystyle\mathrm{P}(\text{conditions~{}\eqref{eqn:Y_rank}
and~{}\eqref{eqn:XY_intersection} hold}|\mathbf{E}=1)$
$\displaystyle=\frac{\mathrm{P}(\text{\eqref{eqn:Y_rank}
and~{}\eqref{eqn:XY_intersection} hold, and
$\mathbf{E}=1$})}{\mathrm{P}(\mathbf{E}=1)}$
$\displaystyle=p_{3}/p_{2}\rightarrow 1$

as $q\rightarrow\infty$. So the lemma follows. ∎

######  Theorem 10.

Let $n$, $m$, $k$ and $t$ be fixed non-negative integers, with
$k\leq\min\\{n,m\\}$ and $t\leq\min\\{m,n\\}$. Define integers $\delta$, $r$
and $s$ by $\delta=\max\\{0,k+t-m\\}$, $r=\min\\{t+k,m,n\\}$ and
$s=\min\\{k,n+\delta-t\\}$. The capacity of the $k$-AMMC tends to $(m+s-k-r)s$
as $q\rightarrow\infty$.

###### Proof.

Let $\mathbf{X}$ be a capacity achieving input distribution to the $k$-AMMC,
and let $\mathbf{Y}$ be the corresponding output distribution. Lemma 6 shows
that we may take $\mathbf{X}$ to be the uniform distribution on the $n\times
m$ matrices of rank $k$. We need to calculate
$I(\mathbf{X};\mathbf{Y})=H(\mathbf{X})-H(\mathbf{X}|\mathbf{Y})$ in this
case.

We see that $H(\mathbf{X})\rightarrow(m-k)k+nk$, by Lemma 5, since
$\mathbf{X}$ is uniform. We now provide a value for the limit of
$H(\mathbf{X}|\mathbf{Y})$.

By Lemma 9,

$\displaystyle H(\mathbf{X}|\mathbf{Y})$
$\displaystyle=\sum_{r=0}^{\min\\{n,m\\}}\sum_{s=0}^{\min\\{r,k\\}}\big{(}\mathrm{P}(\mathrm{rk}(Y)=r,\dim(\mathrm{row}(X)\cap\mathrm{row}(Y))=s))\cdot$
$\displaystyle\quad\quad\quad\quad\quad\quad\quad
H(\mathbf{X}|\mathbf{Y},\mathrm{rk}(\mathbf{Y})=r,\dim(\mathrm{row}(\mathbf{Y})\cap\mathrm{row}(\mathbf{X}))=s)\big{)}$
$\displaystyle\geq
p\,H\big{(}\mathbf{X}|\mathbf{Y},\mathrm{rk}(\mathbf{Y})=\min\\{t+k,m,n\\},$
$\displaystyle\quad\quad\quad\quad\quad\quad\dim(\mathrm{row}(\mathbf{Y})\cap\mathrm{row}(\mathbf{X}))=\min\\{k,n-(t-\delta)\\}\big{)},$

where $p\rightarrow 1$ as $q\rightarrow\infty$. Similarly,

$\displaystyle H(\mathbf{X}|\mathbf{Y})$ $\displaystyle\leq
p\,H\big{(}\mathbf{X}|\mathbf{Y},\mathrm{rk}(\mathbf{Y})=\min\\{t+k,m,n\\},$
$\displaystyle\quad\quad\quad\quad\quad\quad\dim(\mathrm{row}(\mathbf{Y})\cap\mathrm{row}(\mathbf{X}))=\min\\{k,n-(t-\delta)\\}\big{)}$
$\displaystyle\quad+(1-p)mn.$

Since $(1-p)mn\rightarrow 0$ as $q\rightarrow\infty$,

$\displaystyle H(\mathbf{X}|\mathbf{Y})$ $\displaystyle\rightarrow
H\big{(}\mathbf{X}|\mathbf{Y},\mathrm{rk}(\mathbf{Y})=\min\\{t+k,m,n\\},$
$\displaystyle\quad\quad\quad\quad\quad\quad\dim(\mathrm{row}(\mathbf{Y})\cap\mathrm{row}(\mathbf{X}))=\min\\{k,n-(t-\delta)\\}\big{)}.$
(10)

By Lemma 7, the distribution of $\mathbf{X}$ given $\mathrm{rk}(Y)=r$ and
$\dim(\mathrm{row}(Y)\cap\mathrm{row}(\mathbf{X}))=s$ is uniform, for any
fixed $r$ and $s$. In this situation, the number of possibilities for the row
space of $\mathbf{X}$ is

$\genfrac{[}{]}{0.0pt}{}{\,r\,}{s}_{q}\genfrac{[}{]}{0.0pt}{}{\,m-r\,}{k-s}_{q}q^{(k-s)(r-s)}.$

Lemma 2 shows that this tends to $q$ to the power
$(r-s)s+(m-k+s-r)(k-s)+(k-s)(r-s)=(r-s)s+(m-k)(k-s)$. By Lemma 4, the number
of possibilties for $\mathbf{X}$ tends to $q$ to the power
$(r-s)s+(m-k)(k-s)+nk$, and so the entropy of $\mathbf{X}$ given
$\mathrm{rk}(Y)=r$ and $\dim(\mathrm{row}(Y)\cap\mathrm{row}(\mathbf{X}))=s$
tends to $(r-s)s+(m-k)(k-s)+nk$. Hence, by (10),
$H(\mathbf{X}|\mathbf{Y})\rightarrow(r-s)s+(m-k)(k-s)+nk$ where
$r=\min\\{t+k,m,n\\}$ and $s=\min\\{k,n-(t-\delta)\\}$. Thus

$\displaystyle I(\mathbf{X};\mathbf{Y})$
$\displaystyle\rightarrow\left((m-k)k+nk\right)-\left((r-s)s+(m-k)(k-s)+nk\right)$
$\displaystyle=(m-k)s-(r-s)s$

and the theorem follows. ∎

##  5 The AMMC

######  Theorem 11.

Let $n$,$m$ and $t$ be fixed non-negative integers such that
$t\leq\min\\{m,n\\}$. When $m+t\geq 2n$, the capacity of the AMMC tends to
$(m-n)(n-t)$ as $q\rightarrow\infty$. Otherwise, the capacity of the AMMC
tends to $\lceil(m-t)/2\rceil\cdot\lfloor(m-t)/2\rfloor$ as $q$ tends to
$\infty$.

###### Proof.

We need to find the maximal mutual information $I(\mathbf{X};\mathbf{Y})$ over
all input distributions $\mathbf{X}$ to the AMMC, where $\mathbf{Y}$ is the
corresponding output distribution.

Let $c$ be the maximum capacity of the $k$-AMMC, as $k$ ranges over the set
$\\{0,1,\ldots,\min\\{n,m\\}\\}$. If $\mathbf{X}$ is a capacity achieving
distribution for the $k$-AMMC, then we may use this input distribution to the
AMMC. So the capacity of the $k$-AMMC is a lower bound for the capacity of the
AMMC. In particular, $c$ is a lower bound for the capacity of the AMMC.

We aim to derive an upper bound for the capacity of the AMMC, also involving
$c$. Let $\mathbf{X}$ be an input distribution to the AMMC and $\mathbf{Y}$
the corresponding output distribution. Now

$\displaystyle I(\mathbf{X};\mathbf{Y},\mathrm{rk}(\mathbf{X}))$
$\displaystyle=H(\mathbf{Y},\mathrm{rk}(\mathbf{X}))-H(\mathbf{Y},\mathrm{rk}(\mathbf{X})|\mathbf{X})$
$\displaystyle=H(\mathbf{Y},\mathrm{rk}(\mathbf{X}))-H(\mathbf{Y}|\mathbf{X})$
$\displaystyle=H(\mathbf{Y})+H(\mathrm{rk}(\mathbf{X})|\mathbf{Y})-H(\mathbf{Y}|\mathbf{X})$
$\displaystyle=I(\mathbf{X};\mathbf{Y})+H(\mathrm{rk}(\mathbf{X})|\mathbf{Y})$
$\displaystyle\geq I(\mathbf{X};\mathbf{Y}),$

and so using the chain rule we find

$\displaystyle I(\mathbf{X};\mathbf{Y})$ $\displaystyle\leq
I(\mathbf{X};\mathbf{Y},\mathrm{rk}(\mathbf{X}))$
$\displaystyle=I(\mathbf{X};\mathrm{rk}(\mathbf{X}))+I(\mathbf{X};\mathbf{Y}|\mathrm{rk}(\mathbf{X}))$
$\displaystyle\leq
H(\mathrm{rk}(\mathbf{X}))+I(\mathbf{X};\mathbf{Y}|\mathrm{rk}(\mathbf{X}))$
$\displaystyle\leq\log_{q}(\min\\{n,m\\}+1)+I(\mathbf{X};\mathbf{Y}|\mathrm{rk}(\mathbf{X})),$
(11)

since $\mathrm{rk}(\mathbf{X})$ is a random variable with support at most
$\min\\{n,m\\}+1$.

We claim that $c$ is an upper bound for
$I(\mathbf{X};\mathbf{Y}|\mathrm{rk}(\mathbf{X}))$. To see this, note that

$\displaystyle I(\mathbf{X};\mathbf{Y}|$
$\displaystyle\mathrm{rk}(\mathbf{X}))=H(\mathbf{Y}|\mathrm{rk}(\mathbf{X}))-H(\mathbf{Y}|\mathbf{X},\mathrm{rk}(\mathbf{X}))$
$\displaystyle=H(\mathbf{Y}|\mathrm{rk}(\mathbf{X}))-\big{(}H(\mathbf{X},\mathbf{Y}|\mathrm{rk}(\mathbf{X}))-H(\mathbf{X}|\mathrm{rk}(\mathbf{X}))\big{)}$
$\displaystyle=\\!\\!\\!\\!\sum_{k=0}^{\min\\{m,n\\}}\mathrm{P}(\mathrm{rk}(\mathbf{X})=k)\cdot$
$\displaystyle\quad\quad\big{(}H(\mathbf{X}|\mathrm{rk}(\mathbf{X})=k)+H(\mathbf{Y}|\mathrm{rk}(\mathbf{X})=k)-H(\mathbf{X},\mathbf{Y}|\mathrm{rk}(\mathbf{X})=k)\big{)},$

where the second equality follows from [5, Corollary to 2.2.1]. But the
expression

$H(\mathbf{X}|\mathrm{rk}(\mathbf{X})=k)+H(\mathbf{Y}|\mathrm{rk}(\mathbf{X})=k)-H(\mathbf{X},\mathbf{Y}|\mathrm{rk}(\mathbf{X})=k)$

is bounded above by the capacity of the $k$-AMMC, which in turn is at most
$c$. So

$I(\mathbf{X},\mathbf{Y}|\mathrm{rk}(\mathbf{X}))\leq\sum_{k=0}^{\min\\{m,n\\}}\mathrm{P}(\mathrm{rk}(\mathbf{X})=k)\cdot
c=c,$ (12)

and so our claim follows.

The inequalities (11) and (12) combine to show that the capacity of the AMMC
is bounded above by $c+\log_{q}\min\\{n,m\\}$. Since
$\log_{q}\min\\{n,m\\}\rightarrow 0$ as $q\rightarrow\infty$, and since we
have a lower bound of $c$ on the capacity, we see that the capacity of the
AMMC tends to $c$ as $q\rightarrow\infty$. So to prove the theorem, it
suffices to determine the value of $c$.

Define $\delta$, $r$ and $s$ as in Theorem 10. Suppose first that $k$ is such
that $k+t>m$ and so $\delta=(k+t)-m$. We claim that the capacity of the
$k$-AMMC tends to $0$ in this situation. To prove this claim, assume first
that $m\leq n$. Then $r=\min\\{k+t,n,m\\}=m$ and $s=\min\\{k,n+k+t-m-t\\}=k$.
But then $m+s-k-r=0$ and so the capacity tends to $0$ by Theorem 10. Now
assume that $n\leq m$. Here $r=n$ and $s=k+n-m$. So again $m+s-k-r=m-n=0$ and
the capacity again tends to $0$, establishing our claim.

Now assume that $k+t\leq m$, and so $\delta=0$. We have
$r=\min\\{t+k,n\\}=t+\min\\{k,n-t\\}$ and $s=\min\\{k,n-t\\}$. So $r-s=t$, and
Theorem 10 implies that the capacity of the $k$-AMMC tends to $(m-t-k)s$. When
$k\geq n-t$ this capacity is $(m-t-k)(n-t)$, which is a decreasing function of
$k$. As we are maximising the capacity, we may assume without loss of
generality that $k\leq n-t$ and the capacity is $(m-t-k)k$. Note that, since
we are in the situation when $k+t\leq m$ and $k\leq n-t$, the integer $k$ lies
in the interval $[0,\min\\{n-t,m-t\\}]$.

The function $f(x)=(m-t-x)x$ has a unique maximum at $x=(m-t)/2$. Now $x\geq
0$ as $t\leq\min\\{m,n\\}\leq m$, and clearly $x\leq m-t$. Moreover $x<n-t$ if
and only if $m+t<2n$. We have two cases to consider. We first suppose that
$m+t\geq 2n$. Then $x\geq n-t\geq\min\\{n-t,m-t\\}$ and so $x$ lies above the
interval $[0,\min\\{n-t,m\\})$. Hence in this case $f$ is an increasing
function on $[0,\min\\{n-t,m-t\\}]$ and so the capacity is maximal when
$k=\min\\{n-t,m-t\\}$. But note that $m\geq 2n-t\geq n$ (as $m+t\geq 2n$ and
$t\leq\min\\{n,m\\}$) and so the capacity is maximised when
$k=\min\\{n-t,m-t\\}=n-t$ at the value $(m-n)(n-t)$. Hence the AMMC capacity
is $(m-n)(n-t)$ when $m+t\geq 2n$, and the first case of the theorem follows.
Secondly, we suppose that $m+t<2n$. In this case $x$ lies in
$[0,\min\\{n-t,m\\}]$ and so the capacity is maximised when $k=\lfloor
x\rfloor=\lfloor(m-t)/2\rfloor$ at the value
$\lceil(m-t)/2\rceil\cdot\lfloor(m-t)/2\rfloor$. This establishes the second
case of the theorem, as required. ∎

##  6 When the field size is fixed

Throughout this section, we assume that the cardinality $q$ of the underlying
finite field is fixed. Let $\nu,\mu,\tau\in(0,1)$ be fixed real numbers such
that $\tau\leq\min\\{\nu,\mu\\}$. For a positive integer $\ell$ (which we
think of as a size parameter), set $n=\lfloor\nu\ell\rfloor$,
$m=\lfloor\mu\ell\rfloor$, $t=\lfloor\tau\ell\rfloor$. We aim (Theorem 15
below) to determine a good approximation for the capacity of the AMMC as
$\ell\rightarrow\infty$ with $\nu$, $\mu$ and $\tau$ fixed. Indeed, we will
show that the capacity of the AMMC is
$(\mu-\nu)(\nu-\tau)\ell^{2}+O(\ell\log_{q}\ell)$ when $\mu+\tau\geq 2\nu$,
and is $\frac{1}{4}(\mu-\tau)\ell^{2}+O(\ell\log_{q}\ell)$ otherwise. This
generalises and strengthens [13, Proposition 4], which shows, in our notation,
that the capacity is $(\mu-\nu)(\nu-\tau)\ell^{2}+o(\ell^{2})$ when $\mu\geq
2\nu$. (Note that the definition of $\tau$ in [13] and our paper are
different. Note also that the authors in [13] phrase their result in terms of
_normalised capacity_ , which is the result of dividing the capacity by $nm$.
So their formulae differ from ours by a factor of $\nu\mu\ell^{2}$.)

We will mimic the proofs in Sections 4 and 5, and only include details at
points where the proofs differ. We note that Lemmas 6 and 7 hold in our
situation without change. We will prove analogues of Lemmas 8 and 9 and
Theorem 10 in order to provide good bounds on the $k$-AMMC in our asymptotic
regime. Just as in Section 4, the most difficult part of the proof is the
analogue of Lemma 9. In Section 4 we showed that the rank of the matrix $Y$
and the dimension of the intersection $\mathrm{row}(X)\cap\mathrm{row}(Y)$ can
both be predicted with high probability in the $k$-AMMC when
$q\rightarrow\infty$ with $n,m$ and $t$ fixed. In the asymptotic regime we are
considering in this section, this is no longer true. But we are able to
exploit the fact that the approximate values of $\mathrm{rk}(Y)$ and
$\dim(\mathrm{row}(X)\cap\mathrm{row}(Y))$ can be found with high probability.

The following lemma is an analogue of Lemma 8:

######  Lemma 12.

Define $\mu$, $\tau$, $\ell$, $m$ and $t$ as above. Let $k$ be a non-negative
integer such that $k\leq m$. Let $U$ and $V$ be uniformly and independently
sampled from the set of all subspaces of $\mathbb{F}_{q}^{m}$ of dimensions
$k$ and $t$ respectively. Define $\delta=\max\\{0,(k+t)-m\\}$. Then whenever
$\ell>\sqrt{t}q^{2}$,

$\dim(U\cap V)\in[\,\delta,\delta+3\sqrt{\log_{q}\ell}\,],$

with probability at least $1-1/\ell^{7}$.

###### Proof.

We see that $\dim(U+V)=\dim U+\dim V-\dim(U\cap V)$. So
$m\geq\dim(U+V)=k+t-\dim(U\cap V)$. Hence $\dim(U\cap V)\geq\delta$ in all
cases. So it remains to show that $\dim(U\cap
V)\leq\delta+3\sqrt{\log_{q}\ell}$ with high probability.

For any fixed subspace $V$, the number of choices for $U$ with $\dim(U\cap
V)=\delta+b$, say, is

$\genfrac{[}{]}{0.0pt}{}{\,t\,}{\delta+b}_{q}\genfrac{[}{]}{0.0pt}{}{\,m-t\,}{k-\delta-b}_{q}q^{(k-\delta-b)(t-\delta-b)},$

for $0\leq b\leq\min\\{k,t\\}-\delta$, and is zero otherwise. By Lemma 2, the
logarithm to the base $q$ of this expression is bounded above by

$(t-\delta-b)(\delta+b)+\log_{q}4+(m-t-k+\delta+b)(k-\delta-b)+\log_{q}4+(k-\delta-b)(t-\delta-b).$

Since the number of subspaces of $\mathbb{F}_{q}^{m}$ of dimension $k$ is at
least $q^{(m-k)k}$, by Lemma 2, we see that the logarithm to the base $q$ of
the probability that $\dim(U\cap V)=\delta+b$ is at most

$\begin{split}(t-\delta-b)(\delta+b)&+\log_{q}4+(m-t-k+\delta+b)(k-\delta-b)+\log_{q}4\\\
&+(k-\delta-b)(t-\delta-b)-(m-k)k,\end{split}$

which is equal to

$(k+t-m-\delta-b)(\delta+b)+2\log_{q}4.$ (13)

We claim that the expression (13) is bounded above by $-b^{2}+4$. To see this,
first note that when $k+t\leq m$, and so $\delta=0$, the expression (13) can
be written as $-b^{2}+b((k+t)-m)+2\log_{q}4$, which is bounded above by
$-b^{2}+4$ since $\log_{q}4\leq 2$. When $k+t>m$, and so $\delta=k+t-m$, the
same bound holds, since the expression (13) can be written as
$-b^{2}+(m-(k+t))b+2\log_{q}4$ which is bounded above by $-b^{2}+4$ also. So
the claim is established.

Hence the probability that $\dim(U\cap V)>\delta+3\sqrt{\log_{q}\ell}$ is at
most

$\sum_{b=3\sqrt{\log_{q}\ell}}^{\min\\{k,t\\}-\delta}q^{4-b^{2}}\leq
tq^{4}q^{-9\log_{q}\ell}=(tq^{4}/\ell^{2})/\ell^{7}.$

Since $\ell>\sqrt{t}q^{2}$, we see that $tq^{4}/\ell^{2}<1$ and so the lemma
follows. ∎

Next, we use Lemma 12 to prove an analogue of Lemma 9:

######  Lemma 13.

Define $\nu$, $\mu$, $\tau$, $\ell$, $n$, $m$ and $t$ as above. Let $k$ be an
integer such that $0\leq k\leq\min\\{n,m\\}$, and define
$\delta=\max\\{0,k+t-m\\}$ as before. Define $f=13\log_{q}\ell$. Let $X$ and
$W$ be $n\times m$ matrices, chosen uniformly and independently at random
subject to $\mathrm{rk}(X)=k$ and $\mathrm{rk}(W)=t$. Let $Y=A(X+W)$, where
$A$ is chosen uniformly at random from all $n\times n$ invertible matrices.
Whenever $\ell>16+\sqrt{1+t+n}+q^{9}$, we have

$\displaystyle\mathrm{rk}(Y)\in\min\\{t+k,n,m\\}+[-f,0],\text{ and }$ (14)
$\displaystyle\dim(\mathrm{row}(X)\cap\mathrm{row}(Y))\in\min\\{k,n-(t-\delta)\\}+[-f,f].$
(15)

with probability $p$, where $p>1-1/\ell^{3}$.

###### Proof.

As in the proof of Lemma 9, we may assume without loss of generality that $A$
is the identity matrix, and so $Y=X+W$.

Just as in the proof of Lemma 9, we choose the matrices $X$ and $W$ using the
following random process. First we choose subspaces $U$ and $V$ of
$\mathbb{F}_{q}^{m}$ of dimensions $k$ and $t$ respectively, uniformly and
independently at random. We then choose the rows $x_{i}$ of $X$ independently
and uniformly from $U$, and the rows $w_{i}$ of $W$ independently and
uniformly from $V$. Let $\mathbf{E}$ be the indicator variable for the event
that $\mathrm{row}(X)=U$ and $\mathrm{row}(W)=V$. When $\mathbf{E}=1$ the
matrices $X$ and $W$ are uniform such that $\mathrm{row}(X)=U$ and
$\mathrm{row}(W)=V$. So the probability $p$ we are interested in is the
probability that (14) and (15) hold, given that $\mathbf{E}=1$.

Following the proof of Lemma 9, we see that

$\mathrm{P}(\mathbf{E}=1)\geq\prod_{j=1}^{k}(1-q^{-j})\prod_{j=1}^{t}(1-q^{-j}).$

Unlike in Lemma 9, the right hand side of this expression does not tend to 1.
However, by Lemma 1, $\mathrm{P}(\mathbf{E}=1)>(1/4)^{2}=1/16$.

Let $\pi$ be the ‘bad’ probability that our random process produces matrices
$X$ and $Y$ such that (14) or (15) fail. Then the probability $1-p$ that (14)
or (15) fail given $\mathbf{E}=1$ is at most $\pi/\mathrm{P}(\mathbf{E}=1)\leq
16\pi$. We aim to show that $\pi\leq 1/\ell^{4}$ for the values of $\ell$ we
consider. This is sufficient to prove the lemma, since $16\pi\leq
16/\ell^{4}\leq 1/\ell^{3}$ as we are assuming that $\ell\geq 16$.

With probability at least $1-1/\ell^{7}$, $\dim(U\cap V)=z$, where
$z\in[\delta,\delta+3\sqrt{\log_{q}\ell}]$, by Lemma 12. Assume that
$z\in[\delta,\delta+3\sqrt{\log_{q}\ell}]$, so

$t-\delta-3\sqrt{\log_{q}\ell}\leq\dim(V\bmod U)\leq t-\delta.$

Define $r_{i}$ to be the dimension of the space spanned by the first $i$ rows
of $Y$, so $r_{i}=\dim\langle y_{1},y_{2},\ldots,y_{i}\rangle$. Now
$y_{i}=x_{i}+w_{i}=w_{i}\bmod U$, and so the vectors $y_{i}\bmod U$ are
uniformly and independently chosen elements from $V\bmod U$. The probability
that the first $t-\delta-3\sqrt{\log_{q}\ell}-6\log_{q}\ell$ of the vectors
$y_{i}$ are linearly independent modulo $U$ is

$\displaystyle\prod_{i=1}^{t-\delta-3\sqrt{\log_{q}\ell}-6\log_{q}\ell}(q^{\dim(U\cap
V)}-q^{i})/q^{\dim(U\cap V)}$
$\displaystyle\geq\left(1-q^{-6\log_{q}\ell}\right)^{t}$ $\displaystyle\geq
1-t/\ell^{6}.$

So $r_{i}=i$ for $i\leq t-\delta-3\sqrt{\log_{q}\ell}-6\log_{q}\ell$ with
probability at least $1-t/\ell^{6}$. Suppose that this high probability event
occurs: $r_{i}=i$ for $i\leq t-\delta-3\sqrt{\log_{q}\ell}-6\log_{q}\ell$.
Consider the next $\min\\{k,n-(t-\delta)\\}-6\log_{q}\ell$ rows of $Y$. For at
most $3\sqrt{\log_{q}\ell}+6\log_{q}\ell$ of these vectors $y_{i}$, it is
possible that $y_{i}\bmod U$ is not in the span of
$y_{1},y_{2}\ldots,y_{i-1}\bmod U$ and so $r_{i}=r_{i-1}+1$ with probability
$1$. Otherwise, the argument in the proof of Lemma 9 shows that there is a
linear combination of $y_{i}$ and previous rows that produces a uniformly
chosen element of $U$; with probability at least
$1-q^{-6\log_{q}\ell}=1-1/\ell^{6}$ this vector does not lie in the span of
previous rows. Hence the event $E_{0}$ that

$\displaystyle\text{$r_{i}=i$ for }i\leq
t-\delta-3\sqrt{\log_{q}\ell}-6\log_{q}\ell+\min\\{k,n-(t-\delta)\\}-6\log_{q}\ell$
$\displaystyle\text{ and }\dim(U\cap
V)\in[\delta,\delta+3\sqrt{\log_{q}\ell}]$

occurs with probability at least

$(1-1/\ell^{7})(1-t/\ell^{6})(1-1/\ell^{6})^{\min\\{k,n-(t-\delta)\\}-6\log_{q}\ell}.$

We see that this probability is bounded below by
$(1-1/\ell^{7})(1-t/\ell^{6})(1-n/\ell^{6})$, which is at least
$1-1/\ell^{7}-t/\ell^{6}-n/\ell^{6}$. Now $\ell\geq\sqrt{1+t+n}$, and so

$\displaystyle 1-1/\ell^{7}-t/\ell^{6}-n/\ell^{6}$ $\displaystyle\geq
1-(1+t+n)/\ell^{6}$ $\displaystyle\geq 1-\ell^{2}/\ell^{6}.$

So $E_{0}$ occurs with probability at least $1-1/\ell^{4}$.

When the event $E_{0}$ occurs, since $\mathrm{rk}(Y)\geq r_{i}$ for any $i$,
we see that

$\displaystyle\mathrm{rk}(Y)$ $\displaystyle\geq
t-\delta-3\sqrt{\log_{q}\ell}-6\log_{q}\ell+\min\\{k,n-(t-\delta)\\}-6\log_{q}\ell$
$\displaystyle\geq\min\\{k+t-\delta,n\\}-f$

since $\ell\geq q^{9}$ (which implies that
$3\sqrt{\log_{q}\ell}\leq\log_{q}\ell$). Note that the definition of $\delta$
shows that $\min\\{k+t-\delta,n\\}=\min\\{k+t,n,m\\}$. Since
$\mathrm{row}(Y)\subseteq U+V$, we see that $\mathrm{rk}(Y)\leq k+t$.
Moreover, the rank of an $n\times m$ matrix can be at most $\min\\{n,m\\}$.
Hence (14) holds when $E_{0}$ occurs.

We have $\mathrm{row}(X)+\mathrm{row}(Y)=\mathrm{row}(X)+\mathrm{row}(W)$.
Hence, considering the dimensions of these subspaces, we find

$\mathrm{rk}(X)+\mathrm{rk}(Y)-\dim(\mathrm{row}(X)\cap\mathrm{row}(Y))=\mathrm{rk}(X)+\mathrm{rk}(W)-\dim(U\cap
V),$

and so

$\displaystyle\dim(\mathrm{row}(X)\cap\mathrm{row}(Y))$
$\displaystyle=\mathrm{rk}(Y)-\mathrm{rk}(W)+\dim(U\cap V)$
$\displaystyle=\mathrm{rk}(Y)-t+\dim(U\cap V).$

When $E_{0}$ holds,

$\dim(U\cap
V)\in[\delta,\delta+3\sqrt{\log_{q}\ell}]\subseteq[\delta,\delta+f]$

and $\mathrm{rk}(Y)\in\min\\{k+t-\delta,n\\}+[-f,0]$. Hence

$\dim(\mathrm{row}(X)\cap\mathrm{row}(Y))\in\min\\{k,n-(t-\delta)\\}+[-f,f],$

and so $\eqref{eqn:qfixed_XY_intersection}$ holds. Hence the lemma follows. ∎

We are now in a position where we can find a good approximation for the
capacity of the $k$-AMMC. The following theorem is an analogue of Theorem 10:

######  Theorem 14.

Let $q$ be a fixed prime power. Let $\nu,\mu,\tau\in(0,1)$ be fixed real
numbers with the property that $\tau\leq\min\\{\nu,\mu\\}$. For a positive
integer $\ell$, set $n=\lfloor\nu\ell\rfloor$, $m=\lfloor\mu\ell\rfloor$ and
$t=\lfloor\tau\ell\rfloor$. Let $k$ be an integer such that $0\leq
k\leq\min\\{n,m\\}$. Define integers $\delta$, $r$ and $s$ by
$\delta=\max\\{0,(k+t)-m\\}$, $r=\min\\{t+k,m,n\\}$ and
$s=\min\\{k,n+\delta-t\\}$. Define $f=13\log_{q}\ell$. The capacity of the
$k$-AMMC lies between

$(m+s-k-r)s-\big{(}2(m+n)f+(m+n)^{2}/\ell^{3}+\log_{q}4\big{)}$

and

$(m+s-k-r)s+\big{(}(m+n)f+\log_{q}4+4(m+n)^{2}/\ell^{3}\big{)}$

whenever $\ell\geq 16+\sqrt{1+t+n}+q^{9}+14^{2}/(\nu+\mu)^{2}$.

Note that $m$ and $n$ are linear in $\ell$, whereas $f$ is logarithmic. So the
theorem says that the capacity of the $k$-AMMC is approximately $(m+s-k-r)s$.

###### Proof.

As before, we take $\mathbf{X}$ to be the uniform input distribution for the
$k$-AMMC, and $\mathbf{Y}$ to be the corresponding output distribution. This
is a capacity achieving distribution, by Lemma 6, and so we can estimate the
capacity by estimating $H(\mathbf{X})-H(\mathbf{X}|\mathbf{Y})$. The number of
$n\times m$ matrices of rank $k$ is at most
$\genfrac{[}{]}{0.0pt}{}{\,m\,}{k}_{q}q^{nk}$, and is at least
$\genfrac{[}{]}{0.0pt}{}{\,m\,}{k}_{q}q^{nk}/4$, since the first $k$ rows of a
matrix whose rows lie in a subspace of dimension $k$ span the subspace with
probability at least 1/4, by Lemma 1. Since $\mathbf{X}$ is uniform, Lemma 2
implies that

$(m-k)k+nk-\log_{q}4\leq H(\mathbf{X})\leq(m-k)k+nk+\log_{q}4,$ (16)

just as in the proof of Theorem 10.

To estimate $H(\mathbf{X}|\mathbf{Y})$, define $I$ to be the set of pairs
$(r^{\prime},s^{\prime})$ of non-negative integers such that:

$\displaystyle r^{\prime}\in\min\\{t+k,n,m\\}+[-f,0],\text{ and}$
$\displaystyle
s^{\prime}\in\big{(}\min\\{k,n-(t-\delta)\\}+[-f,f]]\big{)}\cap[0,\min\\{r,k\\}]$

Define

$\displaystyle\underline{h}=\min_{(r^{\prime},s^{\prime})\in
I}\big{\\{}\mathrm{P}(\mathrm{rk}(Y)$
$\displaystyle=r^{\prime},\dim(\mathrm{row}(X)\cap\mathrm{row}(Y))=s^{\prime}))\cdot$
$\displaystyle
H(\mathbf{X}|\mathbf{Y},\mathrm{rk}(\mathbf{Y})=r^{\prime},\dim(\mathrm{row}(\mathbf{Y})\cap\mathrm{row}(\mathbf{X}))=s^{\prime})\big{\\}}$

and

$\displaystyle\overline{h}=\max_{(r^{\prime},s^{\prime})\in
I}\big{\\{}\mathrm{P}(\mathrm{rk}(Y)$
$\displaystyle=r^{\prime},\dim(\mathrm{row}(X)\cap\mathrm{row}(Y))=s^{\prime}))\cdot$
$\displaystyle
H(\mathbf{X}|\mathbf{Y},\mathrm{rk}(\mathbf{Y})=r^{\prime},\dim(\mathrm{row}(\mathbf{Y})\cap\mathrm{row}(\mathbf{X}))=s^{\prime})\big{\\}}.$

Lemma 13 and the method in the proof of Theorem 10 shows that

$p\underline{h}\leq H(\mathbf{X}|\mathbf{Y})\leq p\overline{h}+(1-p)mn,$ (17)

where $1\geq p\geq 1-1/\ell^{3}$. We note that, in our asymptotic regime,
$mn/\ell^{3}\rightarrow 0$. And so to estimate $H(\mathbf{X}|\mathbf{Y})$ it
suffices to provide a lower bound for $\underline{h}$ and an upper bound for
$\overline{h}$.

When $Y$ is fixed such that $\mathrm{rk}(Y)=r^{\prime}$, the number of choices
for $\mathrm{row}(X)$ such that
$\dim(\mathrm{row}(X)\cap\mathrm{row}(Y))=s^{\prime}$ is

$\genfrac{[}{]}{0.0pt}{}{\,r^{\prime}\,}{s^{\prime}}_{q}\genfrac{[}{]}{0.0pt}{}{\,m-r^{\prime}\,}{k-s^{\prime}}_{q}q^{(k-s^{\prime})(r^{\prime}-s^{\prime})}.$

The number of matrices $X$ with a given row space $U$ of rank $k$ is at most
$q^{kn}$ (as every row of $X$ lies in $U$). At least $1/4$ of the matrices $X$
whose rows lie in $U$ have $\mathrm{row}(X)=U$, since $k$ randomly chosen
vectors from $U$ span $U$ with probability at least $1/4$, by Lemma 1. So the
number of matrices $X$ with a given row space $U$ of rank $k$ is at least
$q^{kn}/4$. By Lemma 2, we see that the number of possibilities for $X$ is at
most $q$ to the power

$\displaystyle(r^{\prime}-s^{\prime})s^{\prime}+$
$\displaystyle\log_{q}4+(m-r^{\prime}-k+s^{\prime})(k-s^{\prime})$
$\displaystyle\quad+\log_{q}4+(k-s^{\prime})(r^{\prime}-s^{\prime})+kn$
$\displaystyle=(r^{\prime}-s^{\prime})s^{\prime}+(m-k)(k-s^{\prime})+kn+2\log_{q}4$

and, similarly, at least $q$ to the power

$(r^{\prime}-s^{\prime})s^{\prime}+(m-k)(k-s^{\prime})+kn-\log_{q}4.$

These expressions are upper and lower bounds for the conditional entropy
$H(\mathbf{X}|\mathbf{Y},\mathrm{rk}(\mathbf{Y})=r^{\prime},\dim(\mathrm{row}(\mathbf{Y})\cap\mathrm{row}(\mathbf{X}))=s^{\prime})$.

When $(r^{\prime},s^{\prime})\in I$ we see that $r-f\leq r^{\prime}\leq r$ and
$s-f\leq s^{\prime}\leq s+f$, where $r$ and $s$ are defined in the statement
of the theorem. Hence

$\displaystyle\overline{h}$
$\displaystyle\leq(r-s+f)(s+f)+(m-k)(k-s+f)+kn+2\log_{q}4$
$\displaystyle=(r-s)s+(m-k)(k-s)+kn+2\log_{q}4+f^{2}+rf+(m-k)f.$

Now, $rf+(m-k)f\leq(m+n)f$, since $r\leq t+k\leq n+k$. Since $f\geq 16$, we
see that $2\log_{q}4<f$ and so $2\log_{q}4+f^{2}\leq f(f+1)$. Hence
$\overline{h}\leq(r-s)s+(m-k)(k-s)+kn+(f+1)f+(m+n)f$. Also

$f+1\leq 14\log_{q}\ell\leq
14\sqrt{\ell}-2=14\ell/\sqrt{\ell}-2\leq(\nu+\mu)\ell-2\leq m+n,$

since $\ell\geq 14^{2}/(\nu+\mu)^{2}$. So

$\overline{h}\leq(r-s)s+(m-k)(k-s)+kn+2(m+n)f.$

Using this bound together with the expressions (16) and (17) we see that

$\displaystyle I(\mathbf{X};\mathbf{Y})$
$\displaystyle=H(\mathbf{X})-H(\mathbf{X}|\mathbf{Y})$
$\displaystyle\geq(m-k)k+nk-\log_{q}4-p\overline{h}-(1-p)mn$
$\displaystyle\geq(m-k)k+nk-\log_{q}4-\overline{h}-mn/\ell^{3}$
$\displaystyle\geq(m-k)s+(s-r)s-\log_{q}4-2(m+n)f-(m+n)^{2}/\ell^{3}.$

Hence the lower bound of the theorem follows.

Turning to $\underline{h}$, we see that

$\displaystyle\underline{h}$
$\displaystyle\geq(r-s-2f)(s-f)+(m-k)(k-s-f)+kn-\log_{q}4$
$\displaystyle=(r-s)s+(m-k)(k-s)+kn$
$\displaystyle\quad-\log_{q}4-2fs+2f^{2}-(r-s)f-(m-k)f$
$\displaystyle\geq(r-s)s+(m-k)(k-s)+kn-(r+s)f-(m-k)f$ (as
$2f^{2}\geq\log_{q}4$) $\displaystyle\geq(r-s)s+(m-k)(k-s)+kn-(m+n)f$

since $s\leq k$ and $r\leq n$. Using this bound and the expressions (16) and
(17), we see that

$\displaystyle I(\mathbf{X};\mathbf{Y})$
$\displaystyle=H(\mathbf{X})-H(\mathbf{X}|\mathbf{Y})$
$\displaystyle\leq(m-k)k+nk+\log_{q}4-p\underline{h}$
$\displaystyle\leq(m-k)k+nk+\log_{q}4$
$\displaystyle\quad\quad-(1-1/\ell^{3})\big{(}(r-s)s+(m-k)(k-s)+kn-(m+n)f\big{)}$
$\displaystyle\leq(m-k)s+(s-r)s+(m+n)f+\log_{q}4+4(m+n)^{2}/\ell^{3}.$

Hence we have established the upper bound on the capacity, and the theorem is
proved. ∎

######  Theorem 15.

Let $q$ be a fixed prime power. Let $\nu,\mu,\tau\in(0,1)$ be fixed real
numbers with the property that $\tau\leq\min\\{\nu,\mu\\}$. For a positive
integer $\ell$, set $n=\lfloor\nu\ell\rfloor$, $m=\lfloor\mu\ell\rfloor$ and
$t=\lfloor\tau\ell\rfloor$. The capacity of the AMMC is
$(\mu-\nu)(\nu-\tau)\ell^{2}+O(\ell\log_{q}\ell)$ when $\mu+\tau\geq 2\nu$,
and is $\frac{1}{4}(\mu-\tau)\ell^{2}+O(\ell\log_{q}\ell)$ otherwise.

###### Proof.

Let $c$ be the maximum capacity of the $k$-AMMC, where $0\leq
k\leq\min\\{m,n\\}$. The argument in the proof of Theorem 11 shows that $c$
and the capacity of the AMMC differ by at most
$\log_{q}(\min\\{n,m\\}+1)=O(\log_{q}\ell)$ (where the implicit constant
depends on $\mu$ and $\nu$, but not on $k$). We use Theorem 14 to estimate the
capacity of the $k$-AMMC. In that theorem, note that
$(m+n)f=O(\ell\log_{q}\ell)$ and $(m+n)^{2}/\ell^{3}=O(1/\ell)$, where the
implicit constants do not depend on $k$. So Theorem 14 shows that the capacity
of the $k$-AMMC is $(m+s-k-r)s+O(\ell\log_{q}\ell)$, where $r$ and $s$ are
defined in the theorem. We may now maximise the value of $(m+s-k-r)s$ to find
$c$: the argument of Theorem 11 shows $c=(m-n)(n-t)+O(\ell\log_{q}\ell)$ when
$m+t\geq 2n$ and $c=\lceil(m-t)/2\rceil\cdot\lfloor(m-t)/2\rfloor$ otherwise.
Since $(m-n)(n-t)=(\mu-\nu)(\nu-\tau)\ell^{2}+O(\ell)$, and
$\lceil(m-t)/2\rceil\cdot\lfloor(m-t)/2\rfloor=(\mu-\tau)^{2}/4+O(\ell)$, the
theorem follows. ∎

##  7 A coding scheme

A straightforward modification of the coding scheme in [13] works in our more
general setting. Consider the situation when $q$ is large. We think of our
data as an $x\times y$ matrix $U$, where $x=n-t$, $y=m-n$ when $m+t\geq 2n$,
and where $x=\lfloor(m-t)/2\rfloor$ and $y=\lceil(m-t)/2\rceil$ otherwise.
Note that in both cases, $x+y=m-t$. Writing $0_{a\times b}$ for the $a\times
b$ zero matrix, and writing $I_{a}$ for the $a\times a$ identity matrix, we
input $X$ into the channel, where $X$ is the $n\times m$ matrix defined by

$X=\left(\begin{array}[]{c|c|c}0_{(n-x)\times t}&0_{(n-x)\times
x}&0_{(n-x)\times y}\\\ \hline\cr 0_{x\times t}&I_{x}&U\end{array}\right).$

So when $m+t\geq 2n$ we have

$X=\left(\begin{array}[]{c|c|c}0_{t\times t}&0_{t\times n-t}&0_{t\times
m-n}\\\ \hline\cr 0_{(n-t)\times t}&I_{n-t}&U\end{array}\right),$

and if not, setting $d=\lfloor(m-t)/2\rfloor$ and
$d^{\prime}=\lceil(m-t)/2\rceil$, we have

$X=\left(\begin{array}[]{c|c|c}0_{(n-d)\times t}&0_{(n-d)\times
d}&0_{(n-d)\times d^{\prime}}\\\ \hline\cr 0_{d\times
t}&I_{d}&U\end{array}\right).$

On receiving the corresponding matrix $Y=A(X+W)$, we row reduce to produce a
matrix $Z$. Lemma 9 shows that with high probability we expect $Y$ to have
rank $t+x$, and $\mathrm{row}(Y)$ to be the direct sum of $\mathrm{row}(X)$
and $\mathrm{row}(W)$. Indeed, Lemma 8 shows that with high probability
$\mathrm{row}(W)$ intersects the $(m-t)$ dimensional subspace $V$ trivially,
where $V=\\{(v_{1},v_{2},\ldots,v_{m}):v_{i}=0\text{ for }i\leq t\\}$. Note
that $\mathrm{row}(X)\subseteq V$. Row reduction does not change the row
space, so the techniques in the proof of Lemma 9 show that with high
probability $Z$ has the form

$Z=\left(\begin{array}[]{c|c|c}I_{t\times t}&\star&\star\\\ \hline\cr
0_{x\times t}&I_{x}&U\\\ \hline\cr 0_{(n-x-t)\times t}&0_{(n-x-t)\times
x}&0_{(n-x-t)\times y}\end{array}\right)$

where the first $t$ rows of $Z$ are a basis for $\mathrm{row}(W)$ modulo
$\mathrm{row}(X)$ and the next $x$ rows are a basis for $\mathrm{row}(X)$. (If
it is not of this form, we declare a decoding failure.) It is now easy to
recover the data $U$ from the matrix $Z$.

When $q$ is fixed with $n$, $m$ and $t$ large, the same coding method will
work, but the dimensions of $U$ need to be reduced slightly, so that $Z$ is
more likely to have the form above.

## References

  * [1] Rudolf Ahlswede, Ning Cai, S.Y. Li and Raymond W. Yeung, ‘Network information flow’, _IEEE Trans. Inform. Theory_ 46 (2000), 1204–1216.
  * [2] Riccardo Bassoli, Hugo Marques, Jonathan Rodriguez, Kenneth W. Shum and Rahim Tafazolli, ‘Network Coding Theory: A Survey,’ _IEEE Communications Surveys & Tutorials_ 15.4, (2013) 1950–1978.
  * [3] Simon R. Blackburn and Jessica Claridge, ‘Finite field matrix channels for network coding’, _IEEE Trans. Inform. Theory_ 65 (2019), 1614–1625.
  * [4] P. J. Cameron, _Combinatorics: Topics, Techniques, Algorithms._ Cambridge, U.K.: Cambridge Univ. Press, 1994.
  * [5] Thomas M. Cover and Joy A. Thomas, _Elements of Information Theory_ (2nd Edition), John Wiley & Sons Inc., Hoboken, New Jersey, 2006.
  * [6] Chen Feng, Roberto W. Nóbrega, Frank R. Kschischang and Danilo Silva, ‘Communication Over Finite-Chain-Ring Matrix Channels’, _IEEE Trans. Inform. Theory_ 60.10 (2014), 5899–5917.
  * [7] Tracey Ho, Muriel Médard, Ralf Kötter, David R. Karger, Michelle Effros, Jun Shi, and Ben Leong, ‘A random linear network coding approach to multicast’, _IEEE Trans. Inform. Theory_ 52 (2006), 4413-4430.
  * [8] Ralf Kötter and Frank R. Kschischang, Coding for errors and erasures in random network coding, _IEEE Trans. Inform. Theory_ 54 (2008), 3579–3591.
  * [9] S.Y. Li, Raymond W. Yeung, and Ning Cai. ‘Linear network coding’, _IEEE Trans. Inform. Theory_ 49 (2003), 371–381.
  * [10] Roberto W. Nóbrega, Chen Feng, Danilo Silva, and Bartolomeu F. Uchôa-Filho. ‘On Multiplicative Matrix Channels over Finite Chain Rings’, _2013 International Symposium on Network Coding (NetCod)_ (2013), 1–6.
  * [11] Roberto W. Nóbrega, Danilo Silva, and Bartolomeu F. Uchôa-Filho. ‘On the capacity of multiplicative finite-field matrix channels’, _IEEE Trans. Inform. Theory_ 59.8 (2013), 4949–4960.
  * [12] Mahdi J. Siavoshani, Soheil Mohajer, Christina Fragouli and Suhas N. Diggavi. ‘On the capacity of Noncoherent network coding’, _IEEE Trans. Inform. Theory_ 57.2 (2011), 1046–1066.
  * [13] Danilo Silva, Frank R. Kschischang, and Ralf Kötter, ‘Communication over finite-field matrix channels’, IEEE Trans. Inform. Theory 56 (2010), 1296–1305.
  * [14] Shenghao Yang, Siu-Wai Ho, Jin Meng and En-Hui Yang. ‘Capacity Analysis of Linear Operator Channels Over Finite Fields’ _IEEE Trans. Inform. Theory_ 60.8 (2014), 4880–4901.