110 年 國立臺灣大學資訊工程學系碩士班《數學》

A graph is bipartite if and only if it has no cycle of ____ length. A bipartite graph can be colored with ____ colors.

If $a_n=3a_{n/2}+1$ for $n\geq 2$ and $a_1=1$, then $\log_2 a_n\approx$ ____ $\times\log_2 n$.

There are ____ ways a binomial random walk, starting at the origin, returns to the origin for the first time after exactly $2n$ steps.

With $0\leq m,n$, $A=$ ____ and $B=$ ____ in
$\sum_{k=m}^{n}\binom{k}{m}=\binom{A}{B}.$

Let $(G,\circ)$ be a finite group with subgroup $H$. Prove that $|H|$ divides $|G|$.

Suppose $U$ and $V$ are distinct six-dimensional subspaces of a vector space $W$, and $\dim W=8$. Find $\dim(U\cap V)$.

Let $V$ be a vector space of all symmetric $2\times2$ matrices. Define a linear transformation $T:V\to P_2(\mathbb{R})$ by
$T\left(\begin{bmatrix}a&b\\b&c\end{bmatrix}\right)=(a-b)+(b-c)x+(c-a)x^2.$
Find $\operatorname{rank}(T)$.

Suppose $m(t)=t^r+a_{r-1}t^{r-1}+\cdots+a_1t+a_0$ is the minimal polynomial of a nonsingular $n\times n$ matrix $A$. Find $A^{-1}$.

Solve for $t$ if

Which of the following statements are true? Your answer will be considered correct only if all the true statements are selected.

(A) Let $A$ and $B$ be $n\times n$ matrices. Assume that $A$ is invertible and $B^3=0$. If $AB=BA$, then $A+B$ is also invertible.

(B) Let $S$ be the set of all sequences in $\mathbb{R}^{\infty}$ which have exactly $N$ non-zero elements, where $N$ is a known constant. $S$ is a subspace of $\mathbb{R}^{\infty}$.

(C) Any square matrix $A$ can be represented as a sum of a symmetric matrix and a skew-symmetric matrix.

(D) If $A$ and $B$ are similar, they have the same eigenvectors.

(E) If $A,B\in\mathbb{R}^{m\times n}$, $\operatorname{rank}(A-B)\leq\operatorname{rank}(A)-\operatorname{rank}(B)$.

Which of the following statements are true? Your answer will be considered correct only if all the true statements are selected.

(A) Let $D:V\to V$ be defined by $D(f)=\frac{df}{dt}$, where $V$ is the space of functions with basis $\{\sin t,\cos t\}$. The eigenvalues of $D$ are $\pm1$.

(B) $F$ is linear if $F:\mathbb{R}^3\to\mathbb{R}^2$ is defined by $F(x,y,z)=(x+1,y+z)$.

(C) Assume that $A\in M_{n\times n}(\mathbb{F})$ has two distinct eigenvalues, $\lambda_1$ and $\lambda_2$. If $\dim(E_{\lambda_1})=n-1$, $A$ is diagonalizable.

(D) Let $A$, $B$, and $C$ be three $n\times n$ matrices such that, for $k=1,2,\ldots,n$,
$c_{ik}=a_{ik}+b_{ik}$ for some $i$, and $a_{jk}=b_{jk}=c_{jk}$ for $j\neq i$.
Then $\det C=\det A+\det B$.

(E) Let $T$ be a diagonalizable linear operator on a finite-dimensional vector space, and let $m$ be any positive integer. $T$ and $T^m$ are simultaneously diagonalizable.