Appendix D

Exercise D.1-1

For all $i=1,2,\dots,n$ and $j=1,2,\dots,n$ we have

$$\begin{align*} c_{ij} &= a_{ij}+b_{ij} \\ &= a_{ji}+b_{ji} \\ &= c_{ji} \\\\ d_{ij} &= a_{ij}-b_{ij} \\ &= a_{ji}-b_{ji} \\ &= d_{ji} \end{align*}$$

so $C=A+B$ and $D=A-B$ are also symmetric matrices.

Exercise D.1-2

Let $A$ be a matrix of size $p \times q$ and $B$ a matrix of size $q \times r$.We have

$$\begin{align*} c_{ji}^T =c_{ij}&= \sum_{k=1}^qa_{ik}b_{kj} && \text{(} C^T=(AB)^T \text{)} \\ &= \sum_{k=1}^q{b_{jk}^T}{a_{ki}^T} && \text{(} C^T=(B^TA^T) \text{)} \end{align*}$$

Also, $(A^TA)^T=A^T(A^T)^T=A^TA$, so $A^TA$ is always a symmetric matrix.

Exercise D.1-3

Let $A$ and $B$ be $n \times n$ lower-triangular matrices and $C=AB$. For all $1 \le i < j \le n$ we have

$$\begin{align*} c_{ij} &= \sum_{k=1}^na_{ik}b_{kj} \\ &= \sum_{k=1}^{j-1}a_{ik}b_{kj}+\sum_{k=j}^na_{ik}b_{kj} \\ &= \sum_{k=1}^{j-1}a_{ik}\cdot0+\sum_{k=j}^n0\cdot b_{kj} \\ &= 0 \end{align*}$$

Therefore, the matrix $C$ is also lower-triangular.

Exercise D.1-4

As explained in the book, multiplying a vector $x$ by a permutation matrix has the effect of permuting (rearranging) the elements of $x$. We can represent a matrix as a sequence of column vectors $A=\braket{c_1,c_2,\dots,c_n}$. Thus, $PA=\braket{Pc_1,Pc_2,\dots,Pc_n}$ is a matrix where each column vector of $A$ is permuted in the same way. In other words, rows of $A$ are permuted. Analogously, we can view a matrix as a sequence of row vectors $A=\braket{r_1^T,r_2^T,\dots,r_n^T}$, hence $AP=\braket{r_1^TP,r_2^TP,\dots,r_n^TP}$ is a matrix where each row vector of $A$ is permuted in the same way. In other words, columns of $A$ are permuted.

The previous explanation proves the statement from the book at high level. Let us see where elements of $A$ land in $PA$. Row $i$ of $P$ contains only a single 1 at index $q$, so $p_{iq}=1$ and 0s elsewhere. We have

$$\begin{align*} a_{ij} &= \sum_{k=1}^np_{ik}a_{kj} \\ &= p_{iq}a_{qj} \\ &= a_{qj} \end{align*}$$

Notice that all elements from row $q$ of $A$ goes into row $i$. In other words, rows of $A$ are permuted. This works since each distinct row of $P$ has a unique column index such that $P$ has 1 there. A similar observation applies to $AP$ just that instead of permuting rows we permute columns.

Apparently, if we replace $A$ with $P$, then $PP$ is another permutation matrix, as permuting columns or rows of $P$ still maintains the property that it will have exactly one 1 in each row or column, and 0s elsewhere.

Exercise D.2-1

Suppose, for contradiction, that $B \neq C$. We have

$$B=BI=B(AC)=(BA)C=IC=C$$

which contradicts our initial assumption of distinct inverses. Therefore, matrix inverses are unique.

Exercise D.2-2

Let $A$ be an $n \times n$ lower-triangular matrix. We prove by induction on $n$ that $\det (A)$ is equal to the product of its diagonal elements. The base case holds; when $n=1$ then $\det(A)=a_{11}$. For $n >1$ we have

$$\begin{align*} \det(A) &= \sum_{j=1}^n(-1)^{1+j}a_{1j}\det(A_{[1j]}) \\ &= (-1)^{1+1}a_{11}\det(A_{[11]}) \\ &= a_{11}\prod_{i=2}^na_{ii} && \text{(by the inductive hypothesis)} \\ &= \prod_{i=1}^na_{ii} \end{align*}$$

According to the principles of mathematical induction, we can conclude that the statement holds for all $n \ge 1$. For an upper-triangular matrix the poof is nearly identical with a difference that we start at $a_{nn}$ and work backwards.

Suppose, for contradiction, that $B=A^{-1}$ is not lower-triangular, thus ith row of $B$ has additional nonzero entries $b_{i(i+1)},b_{i(i+2)},\dots,b_{ij}$ for $i < j \le n$. We know that $BA=I$ and the ith row of $I$ has only one nonzero element at column $i$. Since $A$ is lower-triangular, the first nonzero element in the jth column is at row $j$, hence $e_{ij}=b_{ij}a_{jj}=0 \implies b_{ij}=0$; $e_{ij}=0$, where $i \neq j$, and $b_{ik}=0$ for all $j <k \le n$. But this entails a cascading effect $b_{i(j-1)}a_{(j-1)(j-1)}+0 \cdot a_{j(j-1)}=0 \implies b_{i(j-1)}=0$ and so on. It turns out that $b_{ij}=0$ for all $j>i$, which contradicts our statement that $B$ is not lower-triangular. Observe that all diagonal elements of $A$ must be nonzero, otherwise $A$ would be singular.

Exercise D.2-3

Wikipedia has a proof here that $P$ is invertible and $P^{-1}=P^T$.

$P^T$ maintains the property that it has exactly one 1 in each row or column, and 0s elsewhere, since transposing a matrix swaps its columns and rows. Therefore, $P^T$ is also a permutation matrix.

Exercise D.2-4

We know that $a_i^T \cdot b_j=0$, where $i \neq j$, and $a_i^T \cdot b_i=1$; $a_*^T$ is a row vector of $A$ and $b_*$ is a column vector of $B$. All row vectors of $A$, except row $i$, are the same in $A'$. All column vectors of $B$, except column $j$, are the same in $B'$. It is stated that $a_i'^T=a_i^T+a_j^T$ and $b_j'=b_j-b_i$ where $i \neq j$. $A'B'=I$ since for all distinct $i$, $j$ and $k$ we still have

$$\begin{align*} a_i'^T \cdot b_j' &= a_i ^T\cdot b_j - a_i^T \cdot b_i + a_j ^T\cdot b_j - a_j^T \cdot b_i=0-1+1-0=0 \\ a_k^T \cdot b_j' &= a_k^T \cdot b_j - a_k^T \cdot b_i=0-0=0 \\ a_i'^T \cdot b_k &= a_i^T \cdot b_k + a_j^T \cdot b_k=0+0=0 \end{align*}$$

On the other hand, $a_i'^T\cdot b_i=a_j^T \cdot b_j'=a_k^T \cdot b_k=1$, hence $A'B'$ has ones on the main diagonal and 0s elsewhere.

Exercise D.2-5

We only prove one direction, as the opposite is symmetrical due to $(A^{-1})^{-1}=A$. Assume every entry of $A$ is real. Let its inverse $B=A^{-1}$ be represented as a sequence of complex column vectors $b_j=x_j+iy_j$ for $j=1,2,\dots,n$. Here, real $n$-vectors $x_j$ and $y_j$ denote the real and imaginary part of $b_j$, respectively. We know that $AB=I$, hence $Ab_j=Ax_j+iAy_j=e_j$ is a real $n$-vector with single 1 at index $j$ and 0s elsewhere. Consequently, $Ay_j=0 \implies y_j=0$ based on Theorem D.1 and Theorem D.2. The previous reasoning applies for all $j=1,2,\dots,n$, thus $B$ is also a real matrix.

Exercise D.2-6

$$\begin{align*} (A^{-1})^T&= (A^T)^{-1} = A^{-1} \\ \\ (BAB^T)^T &= ((BA)B^T)^T \\ &= (B^T)^T(BA)^T \\ &= BA^TB^T \\ &= BAB^T \end{align*}$$

Exercise D.2-7

Let $A=\braket{a_1,a_2,\dots,a_n}$ be a matrix represented as a sequence of column vectors and let $x$ be an $n$-vector, thus $Ax=\sum_{i=1}^n a_ix_i$. If $A$ has a full column rank, then all column vectors are linearly independent. Therefore, $Ax=0 \implies x=0$. In the opposite direction, assume, for contradiction, that the column rank of $A$ is less than $n$ even though $A$ does not have a null vector. Consequently, the column vectors are linearly dependent, so there is some $x \neq 0$ such that $Ax=0$. But this contradicts the initial assumption of $Ax=0 \implies x=0$. This concludes the proof of Theorem D.2.

Exercise D.2-8

Let $A_{m \times p}$ and $B_{p \times n}$ be matrices whose ranks are $r_A$ and $r_B$, respectively. According to the alternate definition of the rank of a matrix, we have that $A=C'_{m \times r_A}D'_{r_A \times p}$ and $B=C''_{p \times r_B}D''_{r_B \times n}$. Let $(AB)_{m \times n}$ be a matrix whose rank is $r$, so $AB=C_{m \times r}D_{r \times n}$. We can express $AB=C'D'C''D''$ in two different ways as follows:

• $AB=(C'D'C'')_{m \times r_B}D''_{r_B \times n} \implies r \le r_B$

• $AB=C_{m \times r_A}'(D'C''D'')_{r_A \times n} \implies r \le r_A$

Therefore, we can conclude that $r \le \min\{r_A,r_B\}$.

Now, assume that $A_{m \times m}$ is a nonsingular matrix, so $r_A=m$. If $B_{m \times m}$ is also a nonsingular matrix then obviously $r_B=m$ and $r=m$, so equality holds. Thus, let $B_{m \times n}$ be a matrix whose rank is $r_B=\min\{m,n\} \le r_A$. We have

$$B = A^{-1}AB = (A^{-1}C)_{m \times r}D_{r \times n} \implies r_B \le r$$

Consequently, $(r \le r_B \land r \ge r_B) \implies r= r_B=\min\{r_A,r_B\}$. The mirror case, where only B is nonsingular, is proven analogously.

Problem D-1

We prove the statement from the book using induction on $n$. The base case $n=1$ trivially holds, as $V(x_0)=\prod_{0\le j<k\le0}(x_k-x_j)=1$.

For $n>1$ we rely on Theorem D.4, while applying the hint from the book, which says that a determinant is unchanged if entries in one row/column are added to those in another row/column. This can be extended to the case where entries are previously scaled by some factor $\lambda \neq 0$. Theorem D.4 also states that a determinant is multiplied by such factor if all entries in some row/column are multiplied by it. So, we can simply multiply all entries by $\lambda$, add such scaled entries to another row/column, and divide the previously multiplied elements by $\lambda$.

We transform the Vandermonde matrix $V$, by following the hint, to get

$$V'=\begin{pmatrix} 1 & 0 & 0 & 0 & \cdots & 0 \\[2mm] 1 & x_1-x_0 & x_1(x_1-x_0) & x_1^2(x_1-x_0) & \cdots & x_1^{n-2}(x_1-x_0) \\[2mm] 1 & x_2-x_0 & x_2(x_2-x_0) & x_2^2(x_2-x_0) & \cdots & x_2^{n-2}(x_2-x_0) \\[2mm] \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\[2mm] 1 & x_{n-1}-x_0 & x_{n-1}(x_{n-1}-x_0) & x_{n-1}^2(x_{n-1}-x_0) & \cdots & x_{n-1}^{n-2}(x_{n-1}-x_0) \end{pmatrix}$$

Each row is scaled by the factor $x_i-x_0$ for $i=1,2,\dots,n-1$, so we have

$$\begin{align*} \det(V(x_1,x_2,\dots,x_{n-1})) &= \det(V') \\ &= \det(V'_{[11]}) \\ &= \prod_{i=1}^{n-1}(x_i-x_0)\det(V(x_1,x_2,\dots,x_{n-1})) \\ &= \prod_{i=1}^{n-1}(x_i-x_0)\!\!\!\!\!\prod_{1\le j<k\le n-1}\!\!\!\!\!\!(x_k-x_j) && \text{(by the inductive hypothesis)}\\ &= \!\!\!\!\!\!\!\!\prod_{0\le j<k\le n-1}\!\!\!\!\!\!(x_k-x_j) \end{align*}$$

According to the principles of mathematical induction, we can conclude that the statement from the book holds for all $n \ge 1$.

Problem D-2

a.

Let $A$ be a matrix represented as a sequence of column vectors $a_i$ for $i=0,1,\dots,n-1$. WLOG assume that the first $r$ column vectors are linearly independent, otherwise we would explicitly work with a set of $r$ indices $J \subseteq\{0,1,\dots,n-1\}$ that denote those linearly independent objects. We prove the upper and lower bound separately.

For any $n$-bit vector $x$ we can always find a matching $n$-bit vector $y$, with 0s on the last $n-r$ positions, such that $Ax=Ay$. This is attainable, as the first $r$ linearly independent column vectors of $A$ can represent all possible combinations of the last $n-r$ dependent vectors. There are at most $2^r$ ways of choosing $y$ for all possible inputs $x$, hence $|R(A)| \le 2^r$.

We claim that any unique combination of the first $r$ bits of an $n$-bit vector $x$ produces a distinct image $Ax$. Suppose, for contradiction, that there is another $n$-bit vector $y$ such that $Ax=Ay$. Assume that both $x$ and $y$ has 0s on the last $n-r$ bit positions. Therefore, $A(x-y)=0$, so $x-y \neq 0$ is a null vector of $A$. But this contradicts the assumption that $A$ has rank $r$, since it turns out that neither the first $r$ column vectors are linearly independent (see also Exercise D.2-7). Thus, $|R(A)| \ge 2^r$.

$(|R(A)| \le 2^r \land |R(A)| \ge 2^r) \implies |R(A)| =2^r$ and $r<n \implies |R(A)| < 2^n=|S_n|$. Therefore, $A$ must have a full rank to define a permutation on $S_n$.

b.

Suppose, for contradiction, there is some $y$ such that $|P(A,y)|>2^{n−r}$. By the pigeonhole principle there would be at least one duplicated segment of $n-r$ bits linked to two different segments of $r$ bits associated with linearly independent columns of $A$. But this would mean that $|R(A)|<2^r$, which is a contradiction (see part (a)). Therefore, $|P(A,y)|\le2^{n−r}$. On the other hand, $|P(A,y)|\ge2^{n−r}$ since no $y$ could have preimage of size less then $2^{n-r}$ without some other having more, which we have just shown is impossible. We know that $|S_n|=2^n$ and everything must add up. We can conclude that $|P(A,y)|=2^{n−r}$.

c.

At first glance, this task seems complicated, but it is essentially a corollary of parts (a) and (b). Let $A$ be a matrix represented as a sequence of column vectors $a_i$ for $i=0,1,\dots,n-1$ as before. An image of $x \in S$ is a linear combination of these vectors $y=Ax=\sum_{i=0}^{n-1} a_ix_i$. The identifier of the block where $y$ belongs spans its last $n-m$ bit positions, while the first $m$ bits specify the offset. Recall that every block is of size $2^m$. This mirrors the structure of each column vector of $A$, hence only the last $n-m$ rows of $A$ determine the block identifier. Inputs $x$ from separate blocks differ by a constant factor $i2^m$, so their images $y$ will be shifted by the same amount. WLOG we may assume that our source block $S$ is block 0. Consequently, all input $n$-bit vectors $x$ have 0s in the last $n-m$ positions, thus only the leftmost $m$ columns of $A$ are relevant. Evidently, all the remaining columns of $A$ would be multiplied by 0s during the matrix-vector multiplication $Ax$.

A fundamental property of any matrix $A$ is that its row rank always equals its column rank. The fact that $r$ is the rank of the lower-left $(n-m) \times m$ submatrix of $A$ implies that there are $r$ linearly independent column vectors among the leftmost $m$ columns of $A$. Every distinct combination of these vectors produces a unique block identifier. As a corollary of part (a) we have that $|B(S',m)|=2^r$. Furthermore, as a corollary of part (b), we can also conclude that for each block in $B(S',m)$, exactly $2^{m-r}$ numbers in $S$ map to that block.

d.

There are $(2^n)!$ permutations of $S_n$. The number of linear permutations is upper bounded by $|A|\times|c|$, where $|A|=2^{n^2}$ (total count of $n \times n$ 0-1 matrices) and $|c|=2^n$ (total count of $n$-bit vectors). For $n \ge 3$ it holds that $(2^n)!>2^{n(n+1)}$.

e.

We start by answering the hint from the book. For a given permutation, multiplying a matrix with a unit vector $e_i$ results in selecting the ith column vector for $i=1,2,\dots,n$. By part (d) the smallest $n$ is 3, so choose $S_3$ with the following partial permutation $\pi_{A,c}$: $\pi_{A,c}(0)=0$, $\pi_{A,c}(1)=2$, $\pi_{A,c}(2)=4$, $\pi_{A,c}(4)=1$. Now all parameters are fixed. Currently, 3 is mapped to 6, so just choose something else. Here is the rest of the permutation that cannot be achieved with a linear permutation model: $\pi_{A,c}(3)=7$, $\pi_{A,c}(7)=3$, $\pi_{A,c}(6)=6$, $\pi_{A,c}(5)=5$.