115年 - 115 國立臺北大學_碩士班一般入學考試試題_資訊工程學系：線性代數與離散數學#147267

科目：【阿摩】未分類題庫 | 年份：115年 | 選擇題數：0 | 申論題數：13

試卷資訊

所屬科目：【阿摩】未分類題庫

選擇題 (0)

申論題 (13)

1. (15%)

Consider the following graph. It has 20 vertices each with degree 3. Answer each of the five following questions and give a brief proof of your answer for each question.

Is it a planar graph?
Does it have a Euler circuit?
Does it have a Euler path?
Does it have a Hamilton circuit?
Does it have a Hamilton path?
2. (15%)

Consider the following relations on the set of integers. Answer each of the three following questions and give a brief proof for each of your answers.

$$R_1=\{(x, y) \mid (x - y)^2 < 10\}$$

$$R_2=\{(x, y) \mid x + y = 0\}$$

$$R_3=\{(x, y) \mid \gcd(x, y) = 1\}$$

$$R_4=\{(x, y) \mid (x - y) \bmod 5 = 0\}$$

$$R_5=\{(x, y) \mid x > y\}$$

Which of these relations are reflexive?
Which of these relations are symmetric?
Which of these relations are transitive?
3. (10%)

A derangement is a permutation of objects that leaves no object in the original position. For example, the permutation 21453 is a derangement of 12345 because no digit is left in its original position. What is the total number of derangements of 1234? List all derangements of 1234.
4. (10%)

Find all integer solutions for $x$ such that $18x \equiv 6 \pmod{141}$.
5. (20%)

In the following, you should use uppercase letters to denote matrices and lowercase letters with subscripts to denote their entries. For example, if $M$ is a matrix, then $m_{ij}$ denotes its $(i,j)$-entry. Use lowercase letters with an arrow to denote column vectors of a matrix. For example, $\vec{m}_i$ denotes the $i$-th column vector of the matrix $M$.

In your proofs, use the following definitions as needed.

Definition (Equality of matrices): Matrices $A$ and $B$ are equal if they have the same size and have equal corresponding entries $a_{ij} = b_{ij}$ for all $(i,j)$.

Definition (Matrix transpose): The transpose of an $m \times n$ matrix $A$ is the $n \times m$ matrix denoted by $A^T$ whose $(i,j)$-entry is the $(j,i)$-entry of $A$.

Definition (Linear combination): A linear combination of vectors $\vec{u}_1, \vec{u}_2, ..., \vec{u}_k$ is a vector of the form $c_1\vec{u}_1 + c_2\vec{u}_2 + \cdots + c_k\vec{u}_k$, where $c_1, c_2, ..., c_k$ are scalars.

Definition (Standard vectors):

$$\vec{e}_1 = \begin{bmatrix} 1 \\ 0 \\ \vdots \\ 0 \end{bmatrix}, \vec{e}_2 = \begin{bmatrix} 0 \\ 1 \\ \vdots \\ 0 \end{bmatrix}, ..., \vec{e}_n = \begin{bmatrix} 0 \\ 0 \\ \vdots \\ 1 \end{bmatrix}$$

Now let $A$ denote a $m \times n$ matrix. Prove that $(A^T)^T = A$ and $A\vec{e}_i = \vec{a}_i$ for $i = 1, ..., n$.
6. (10%)

Use Gauss elimination to find the inverse of the following matrix $A$. First, reduce the matrix to row echelon form, and then continue to reduced row echelon form to obtain the inverse matrix.

$$A = \begin{bmatrix} 1 & 2 & 3 \\ 2 & 5 & 6 \\ 3 & 4 & 8 \end{bmatrix}$$
7. (20%)

Find the eigenvalues of the following matrix $A$ and determine a basis for each eigenspace. Use the characteristic polynomials and Gauss elimination to obtain your answers.

$$A = \begin{bmatrix} -2 & -6 & -6 \\ -3 & 2 & -2 \\ 3 & 2 & 6 \end{bmatrix}$$