3.5-exam1-2008¶
Quiz 1, 2008 · Section 3.5: Dimensions of the Four Subspaces Source: exam1_1.pdf, pp. 190, 192
Problem¶
4 (28 pts.) A Sudoku puzzle solution such as the example on the last page is a 9x9 matrix \(A\) that among other properties has the numbers 1 through 9 once in every row and in every column.
Hint 1: There is no need to compute at all to solve this problem, and familiarity with Sudoku puzzles is unlikely to help or hurt.
Hint 2: \(1 + 2 + 3 + \cdots + 9 = 45\).
(a) All such matrices \(A\) can be written as
where the matrices \(P_1, \ldots, P_9\) are what kind of matrices? (Looking for what we consider the best possible one word answer. Square would be correct, but would not be acceptable.)
(b) Let \(e\) be the \(9 \times 1\) vector of nine 1's. What is the rank of the \(9 \times 3\) matrix whose columns are \(e\), \(Ae\), and \(A^Te\) for any such matrix \(A\). Explain your answer.
Solution
(a) Permutation matrices. (b) Well, \(Pe = e\) for any permutation matrix, because each row has eight zeros and one one. So by part (a), \[ Ae = e + 2e + \cdots + 9e = 45e. \] But since the transpose of a permutation matrix is also a permutation matrix, \(A^Te = 45e\) also. But \(\mathrm{rank}(e \ 45e \ 45e) = 1\).Keywords: permutation matrix, rank, column space, sudoku