114 年 國立中央大學資訊工程學系碩士班《離散數學與線性代數》

Given a linear transformation from $R^2$ to $R^3$ (with respect to standard bases)
$L\left(\begin{bmatrix} x \\ y \end{bmatrix}\right) = \begin{bmatrix} 2x - 2y \\ 3x - 4y \\ -7x \end{bmatrix}$
Now let $B_1 = \left\{ \begin{bmatrix} 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 1 \\ -1 \end{bmatrix} \right\}$ and $B_2 = \left\{ \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix}, \begin{bmatrix} 1 \\ 0 \\ 1 \end{bmatrix}, \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} \right\}$ be non-standard bases for $R^2$ and $R^3$, respectively. If the matrix representation of the same linear transformation $L$ (with respect to $B_1$ and $B_2$) is
$[L]_{B_1, B_2} = \begin{bmatrix} a & b \\ c & d \\ e & f \end{bmatrix}$
what is $\lfloor | a + b + c + d + e + f | \rfloor \% 5$? ( % is the modulo operation. $\lfloor z \rfloor$ rounds $z$ to the smaller nearest integer.)

(a) 0
(b) 1
(c) 2
(d) 3
(e) 4

Let the Gram-Schmidt QR factorization of the matrix
$A = \begin{bmatrix} 1 & -2 & -1 \\ 2 & 0 & 1 \\ 2 & -4 & 2 \\ 1 & 4 & 0 \end{bmatrix}$
be $A = Q R$, where $Q$ is an orthogonal matrix and $R$ is an upper triangular matrix.
$R = \begin{bmatrix} a & b & c \\ 0 & d & e \\ 0 & 0 & f \end{bmatrix}$
What is $\lfloor | a + b + c + d + e + f | \rfloor \% 5$? (% is the modulo operation. $\lfloor z \rfloor$ rounds $z$ to the smaller nearest integer.)

(a) 0
(b) 1
(c) 2
(d) 3
(e) 4

Assume $p(x) = x^{10} - x^5 + 1$ and $A = \begin{bmatrix} -2 & -6 \\ 1 & 3 \end{bmatrix}$. Let $p(A) = \begin{bmatrix} a & b \\ c & d \end{bmatrix}$. What is $\lfloor | a + b + c + d | \rfloor \% 5$? (% is the modulo operation. $\lfloor z \rfloor$ rounds $z$ to the smaller nearest integer.)

(a) 0
(b) 1
(c) 2
(d) 3
(e) 4

Let $A = \begin{bmatrix} 1 & 2 \\ -1 & 1+i \end{bmatrix}$ and the unitary matrix that diagonalizes $A$ be $U = \frac{1}{\sqrt{3}} \begin{bmatrix} 1 & 1+i \\ -1+i & 1 \end{bmatrix}$. Let $U^* A U = \begin{bmatrix} a+ib & c+id \\ e+if & g+ih \end{bmatrix}$. What is $\lfloor | a + c + e + g | \rfloor \% 5$? (% is the modulo operation. $\lfloor z \rfloor$ rounds $z$ to the smaller nearest integer.)

(a) 0
(b) 1
(c) 2
(d) 3
(e) 4

Which of the following vectors belong to the nullspace of $A = \begin{bmatrix} 1 & 1 & 1 & 0 \\ 1 & 2 & 1 & 0 \\ 1 & 0 & 1 & 0 \end{bmatrix}^T$?

(a) $(0,0,0,0)^T$
(b) $(1,1,1,0)^T$
(c) $(1,-2,1,0)^T$
(d) $(-1,1,0,1)^T$
(e) $(0,-1,1,1)^T$

A and B are both $N \times N$ square matrices. Which of the following statements are true?

(a) If $\lambda$ is the eigenvalue of A and $\mu$ is the eigenvalue of B, then $\lambda \times \mu$ is the eigenvalue of AB.
(b) AB and BA have the same eigenvalues.
(c) AB and BA have the same eigenvectors.
(d) If $B = M^{-1} A M$, then A and B have the same eigenvalues.
(e) If $AA^H = A^H A$ ($A^H$ is $A$'s Hermitian Transpose), then A and $A^H$ have the same eigenvalues.

A and B are both $N \times N$ square matrices. Which of the following statements are true?

(a) If $\lambda$ is the eigenvalue of A and $\mu$ is the eigenvalue of B, then $\lambda \times \mu$ is the eigenvalue of AB.
(b) AB and BA have the same eigenvalues.
(c) AB and BA have the same eigenvectors.
(d) If $B = M^{-1} A M$, then A and B have the same eigenvalues.
(e) If $AA^H = A^H A$ ($A^H$ is $A$'s Hermitian Transpose), then A and $A^H$ have the same eigenvalues.

A is an $N \times N$ symmetric matrix. Which of the following statements are true?

(a) If $A^{-1}$ exists, $A^{-1}$ must be symmetric.
(b) A must have a complete set of (N) orthonormal eigenvectors.
(c) If $A^2 = A$, its eigenvalues must be 0 and 1.
(d) If the sum of each individual column of A is 1, then one of its eigenvalues is 1.
(e) If B is also an $N \times N$ symmetric matrix. AB must be symmetric.

We are processing two-dimensional data on the X-Y plane. Which of the following are true?

(a) One particle is initially located at the point A (0,-1) and on the unit circle. It goes straight to B on the unit circle as shown in the figure, and $\angle OAB=15^\circ$, where O is the origin (0,0). The particle is then reflected and reaches $P_1$ on the unit circle with $\angle OBA = \angle OBP_1$. The particle keeps reflecting and reaches point $P_{120}$ on the unit circle and so on. The coordinate of $P_{120}$ is $(\cos(15^\circ), -\sin(15^\circ))$.
(b) The point A (0,-1) is linearly transformed by $J = \begin{bmatrix} 1 & 2 \\ 2 & -1 \end{bmatrix}$. After N linear transformations (i.e., $J^N \begin{bmatrix} 0 \\ -1 \end{bmatrix}$), the position is $Q_N=(X_N, Y_N)$. $Q_{1001}=0$.
(c) Following (B), the distance between $Q_{1000}$ and $Q_{1001}$ is M. The distance between $Q_{999}$ and $Q_{1000}$ is N. $\frac{M}{N} > 2.3$.

🖼️【此處有附圖，請對照原卷】

Let the matrix
$A = \begin{bmatrix} a_1 & b_1 & c_1 & d_1 \\ a_2 & b_2 & c_2 & d_2 \\ a_3 & b_3 & c_3 & d_3 \end{bmatrix}$
be processed by row operations to form
$B = \begin{bmatrix} 1 & 2 & 3 & 5 \\ 0 & 1 & 2 & 7 \\ 0 & 0 & 1 & 3 \end{bmatrix}$
Which of the following are true?

(a) $\det(A) = \det(B)$.
(b) After row operations, $\begin{bmatrix} a_1 & b_1 & c_1 & d_1 \\ a_2 & b_2 & c_2 & d_2 \\ a_3 & b_3 & c_3 & d_3 \end{bmatrix}$ can become $\begin{bmatrix} 2 & -1 & 0 & -5 \\ 0 & 3 & -2 & -1 \\ 0 & 0 & -3 & 9 \end{bmatrix}$.
(c) If $a_1^2 + a_2^2 + a_3^2 = 2$, then $|(a_1, a_2, a_3) \times (d_1, d_2, d_3)| = 4\sqrt{2}$, where $\times$ is the cross product.
(d) The system of linear equations
$\begin{cases} a_1x + c_1y + 3b_1 = d_1 \\ a_2x + c_2y + 3b_2 = d_2 \\ a_3x + c_3y + 3b_3 = d_3 \end{cases}$
has a unique solution.
(e) The system of linear equations
$\begin{cases} (3b_1 + c_1)x - 2a_1y + d_1z + 2c_1 = 0 \\ (3b_2 + c_2)x - 2a_2y + d_2z + 2c_2 = 0 \\ (3b_3 + c_3)x - 2a_3y + d_3z + 2c_3 = 0 \end{cases}$
has a unique solution.

Which of the determinants of the following matrices are zero?

(A) $\begin{bmatrix}0&3&2&6&3\\-3&0&1&3&2\\-2&-1&0&5&3\\-6&-3&-5&0&4\\-3&-2&-3&-4&0\end{bmatrix}$

(B) $\begin{bmatrix}1&3&2&4&3\\5&4&1&3&2\\2&5&2&5&3\\2&6&4&8&6\\4&7&8&7&9\end{bmatrix}$

(C) $\begin{bmatrix}1&1&0&0&0\\-1&3&1&0&0\\0&-1&3&1&0\\0&0&-1&3&1\\0&0&0&-1&3\end{bmatrix}$

(D) $\begin{bmatrix}1&1&0&0&0\\1&1&1&0&0\\0&1&1&1&0\\0&0&1&1&1\\0&0&0&1&1\end{bmatrix}$

(E) $\begin{bmatrix}1&2&3&4&0\\2&4&2&0&0\\3&2&0&0&0\\4&0&4&0&0\\0&0&0&0&1\end{bmatrix}$

About relation $R$, which of the following statements are true?

(A) $R$ is reflexive.

(B) $R$ is anti-symmetric.

(C) $R$ is transitive.

(D) $R$ is a partial ordering relation.

(E) The transitive closure of $R$ is symmetric.

Let $S$ be the transitive closure of $R$, and each element is a set. If $S$ reflects operators’ behavior on $\mathrm{Set}$, what are possible operators?

(A) $\cap$

(B) $\cup$

(C) $\subseteq$

(D) Set difference

(E) $\supset$

Consider the divisibility relation (i.e., $|$) and the poset $R=(S,|)$, where $S=\{1,2,3,4,6,8,12,24\}$. We can conclude that:

(A) $R$ is a total order.

(B) $R$ is a well order.

(C) $R$ has a greatest lower bound.

(D) $R$ is a lattice.

(E) $R$ has a maximal element.

In the following procedure, $P$, $P$, and $B$ are all procedures; each statement line in and outside the loop counts as 1 step.

Procedure $P(\text{array1}[a_1,a_2,\ldots,a_n])$

1. If $n<9$, exit.
2. Call $B(\text{array1}[a_1,a_2,\ldots,a_n])$; declare new empty array2, array3, array4.
3. For $(i=1\text{ to }n)$:
   4. If $(i\bmod 9)=1$, insert $a_i$ into array2;
   5. If $(i\bmod 9)=4$, insert $a_i$ into array3;
   6. If $(i\bmod 9)=7$, insert $a_i$ into array4.
4. Call $P(\text{array2})$.
5. Call $P(\text{array3})$.
6. Call $P(\text{array4}).

In order to make $P$’s complexity $O(n)$, which of the following can be $B$’s complexity? ($m$ is the input size of $B$.)

(A) $O(m^{1/2})$

(B) $O(m^1)$

(C) $O(m^{\sqrt{2}})$

(D) $O(m^{1/4})$

(E) $O(m^2)$

To solve the recurrence relation $a_n=4a_{n-1}-4a_{n-2}$, $a_0=0$, $a_1=1/2$, what of the following are true? (Generating function $G(z)$ for this recurrence relation.)

(A) $G(z)(1-4z+4z^2)=\frac{1}{1+z}-1+\frac{3}{2}z$

(B) $G(z)(1-4z+4z^2)=\frac{1}{1+z}-1+z$

(C) $G(z)=-\frac{1}{9}\frac{1}{1+z}+\frac{7}{9}\frac{1}{(1-2z)^2}+\frac{z}{9}\frac{1}{(1-2z)^2}$

(D) $G(z)=\frac{1}{9}\frac{1}{1+z}+\frac{19}{18}\frac{z}{(1-2z)^2}-\frac{1}{9}\frac{1}{(1-2z)^2}$

(E) $a_n=\frac{1}{9}(-1)^n+\frac{19}{36}n\cdot2^n-\frac{1}{9}2^n$

Which of these graphs have an Euler circuit?

(A) $C_5$

(B) $W_5$

(C) $K_5$

(D) $K_{5,5}$

(E) $Q_5$

At a party, you and your partner meet three other couples. Several handshakes take place under the following rules: no one shakes hands with themselves or their own partner, no one shakes hands with the same person more than once, and the number of handshakes for the other seven people (excluding you) are all different.

Based on these conditions, how many hands did you shake, and how many hands did your partner shake?

(A) You shook 4 hands.

(B) You shook 5 hands.

(C) You shook 3 hands.

(D) Your partner shook 0 hands.

(E) Your partner shook 3 hands.