Problem 26 - Advanced Linear Algebra

Question

Suppose that \(A_{m, n}, B_{p, q}, C_{n, k}\) and \(D_{q, r}\) are matrices of the given sizes. Prove that $$ (A \otimes B)(C \otimes D)=(A C) \otimes(B D) $$ Discuss the case \(k=r=1\).

Step-by-Step Solution

Answer

In order to prove that \((A \otimes B)(C \otimes D) = (A C) \otimes (B D)\), we first calculated the Kronecker products and matrix products separately, and then combined the results. We showed that the elements in both cases are equal, so the given equation holds true. When \(k = r = 1\), both \(C\) and \(D\) are column vectors and the same equality is maintained, validating our proof for this special case as well.

Step 1: Calculate the Kronecker products

First, calculate the Kronecker products of the given matrices. The Kronecker product of \(A_{m, n}\) and \(B_{p, q}\) is given by: $$ (A \otimes B)_{(i - 1)p + j, (l - 1)q + k} = A_{i, l} B_{j, k} $$ Similarly, the Kronecker product of \(C_{n, k}\) and \(D_{q, r}\) is given by: $$ (C \otimes D)_{(i - 1)q + j, (l - 1)r + k} = C_{i, l} D_{j, k} $$

Step 2: Find the product of the Kronecker products

Now, we want to find the product of the Kronecker products on the left-hand side of the given equation. This is given by: $$ [(A \otimes B)(C \otimes D)]_{(a - 1)p + b, (c - 1)r + d} = \sum_{i = 1}^{nq} (A \otimes B)_{(a - 1)p + b, i} (C \otimes D)_{i, (c - 1)r + d} $$ Replace the previously calculated values for \((A \otimes B)\) and \((C \otimes D)\): $$ \sum_{i = 1}^{nq} A_{a, \left\lceil\frac{i}{q}\right\rceil} B_{b, i \bmod q}C_{\left\lceil\frac{i}{q}\right\rceil, c} D_{i \bmod q, d} $$

Step 3: Calculate the matrix products

Now, calculate the matrix products of \(A C\) and \(B D\). The product of \(A_{m, n}\) and \(C_{n, k}\) is given by: $$ (AC)_{a, c} = \sum_{i = 1}^{n} A_{a, i} C_{i, c} $$ Similarly, the product of \(B_{p, q}\) and \(D_{q, r}\) is given by: $$ (BD)_{b, d} = \sum_{i = 1}^{q} B_{b, i} D_{i, d} $$

Step 4: Calculate the Kronecker product of the matrix products

Now, we need to find the Kronecker product of the calculated matrix products. This is given by: $$ [(AC) \otimes (BD)]_{(a - 1)p + b, (c - 1)r + d} = (AC)_{a, c} (BD)_{b, d} $$ Replace the previously calculated values for \((AC)\) and \((BD)\): $$ \left(\sum_{i = 1}^{n} A_{a, i} C_{i, c}\right) \left(\sum_{i = 1}^{q} B_{b, i} D_{i, d}\right) $$

Step 5: Compare the elements

Now, compare the elements obtained in Step 2 and Step 4. On comparing, we can see that both expressions are equal. Therefore, the given equation is proven to be true: $$ (A \otimes B)(C \otimes D)=(A C) \otimes(B D) $$

Step 6: Discuss the case \(k=r=1\)

In this special case, where \(k = r = 1\), the matrices \(C_{n, k}\) and \(D_{q, r}\) are actually column vectors of length \(n\) and \(q\) respectively. Thus, the Kronecker product of \(A_{m, n}\) and \(B_{p, q}\) is still a block matrix, but the product of the Kronecker products and the Kronecker product of the matrix products essentially replicate the same operation as the matrix-vector product with the column vectors \(C\) and \(D\). This maintains the same equality as the general case, validating our proof for this special case as well.

Key Concepts

Matrix Multiplication

Matrix multiplication is a fundamental operation in linear algebra that allows us to combine two matrices to form a new matrix. Unlike element-wise multiplication, matrix multiplication involves a rule-based combination of rows and columns.

For two matrices, A and C with dimensions \(m \times n\) and \(n \times k\) respectively, the product \(AC\) is defined only if the number of columns in A is equal to the number of rows in C. The result is a new matrix with dimensions \(m \times k\), where each element is computed as the sum of products of corresponding entries from the rows of A and the columns of C. Specifically,

\[ (AC)_{a, c} = \sum_{i = 1}^{n} A_{a, i} C_{i, c} \]
This means we sum over the products of the a-th row of A and the c-th column of C. A key aspect to remember is that matrix multiplication is associative but not necessarily commutative; the product \(AC\) may not be equal to \(CA\), and may sometimes not even be defined if A and C are not square matrices. In our textbook exercise, this concept is directly employed to prove the relationship between the Kronecker product of matrices and matrix multiplication.

Tensor Product and the Kronecker Product

The tensor product, often represented as the Kronecker product in the context of matrices, is a more general form of matrix multiplication. It creates a new matrix that expresses the relationship between all combinations of the elements of two matrices.

Given matrices A of size \(m \times n\) and B of size \(p \times q\), their Kronecker product is a larger matrix of size \(mp \times nq\), where each element of A is multiplied by the entire matrix B. Formally, we can express a single element of the Kronecker product as

\[ (A \otimes B)_{(i - 1)p + j, (l - 1)q + k} = A_{i, l} B_{j, k} \]
This operation reflects a 'block matrix' structure where each element of A is replaced by a block that is the product of that element and the entire matrix B. Importantly, the Kronecker product has direct applications in higher-dimensional space representations and is widely used in physics and computer science, particularly in the design of complex systems and quantum computing.

Linear Algebra

Linear algebra is a branch of mathematics concerned with vector spaces and linear mappings between these spaces. It includes the study of lines, planes, and subspaces, but is also concerned with properties that are common to all vector spaces.

Two central concepts in linear algebra are the solution of linear systems and transformations. Matrices and vectors are the language of linear algebra, and operations like matrix multiplication, transposition, and the Kronecker product play key roles in the transformation and rotation of these vectors within space.

In the context of our textbook problem, linear algebra provides the framework for understanding and manipulating these abstract concepts. It allows us to generalize the computations from finite-dimensional space, often represented by matrices and vectors, to potentially infinite-dimensional spaces—hence why it's an indispensable tool in modern mathematics, the natural sciences, engineering, and social sciences. The textbook exercise demonstrates one of the countless applications of linear algebra: proving properties of matrix operations like the Kronecker product.