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

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

試卷資訊

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

選擇題 (0)

申論題 (14)

1. (20%) Consider an RSA cryptographic system with the public key $(n, e) = (649, 387)$. First, find prime numbers $p$ and $q$ such that $n = pq$. Second, find the value of $d$ in the private key $(n, d)$. Third, decrypt the ciphertext 10 into plaintext. Fourth, encrypt the plaintext 351 into ciphertext. Finally, answer the question "Is it possible to find more than one values of $d$ in the range $0 < d < (p - 1)(q - 1)$ that works in decryption?" If your answer is YES, find all possible values of $d$; if your answer is NO, give a brief proof.
2. (20%) Answer the questions about the following graph. 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? Prove your answers.
3. (10%) Solve the recurrence relation $nan - (n+1)a{n-1} = 1$ with the initial condition $a_0 = 1$.
4. Given the following linear system:

$$\left\{ \begin{array}{l} x1 + 4x2 + 3x3 = 2 \\ -x1 - 2x2 = -3 \\ 2x1 + 2x2 + 3x3 = 1 \end{array} \right.$$

The above linear system can be expressed as the matrix representation $A\vec{x} = \vec{b}$.

(a) (5%) The nonsingular matrix A can be reduced to row echelon form with a finite number of elementary row operations.

Thus $U = Ek E{k-1} \cdots E1 A$, where $U$ denotes the upper triangular matrix, and $En$ represents the elementary matrix, $n = 1, \ldots, k$.

Then $\det(U) = \det(Ek)\det(E{k-1}) \cdots \det(E_1)\det(A)$.

Use the above two equations, first find $U$ and then compute $\det(A)$ for the above linear system.
(b) (5%) (Triangular Factorization problem) Let \( A = LU \), where \( L \) and \( U \) denote the lower triangular matrix and upper triangular matrix, respectively. Find \( L \).
(c) (5%) Express the linear system in matrix representation \( A\vec{x} = \vec{b} \), then solve the linear system by computing \( A^{-1} \).
(d) \((5\%)\) Solve the linear system using Cramer's Rule.
5. Given $\vec{a}1 = (1, 4, 3)^T$, $\vec{a}2 = (-1, -2, 0)^T$, $\vec{a}3 = (0, 0, 1)^T$, $\vec{a}4 = (2, 2, 3)^T$.

(a) \((2\%)\) Is \(\{\vec{a}1,\vec{a}2,\vec{a}_4\}\) a spanning set for \(\mathbb{R}^3?\) Explain why or why not.
(b) \((3\%)\) Are vectors \(\vec{a}1, \vec{a}2, \vec{a}3\), and \(\vec{a}4\) linearly independent? Explain why or why not.
(c) \((5\%)\) Let matrix \(A = (\vec{a}1,\vec{a}2,\vec{a}_3)\). Find the eigenvalues of \(A\).
(d) \((5\%)\) Let \(\lambda1, \lambda2, \dots, \lambda_n\) be the eigenvalues of matrix A.

Prove that $\det(A) = \lambda1 \cdot \lambda2 \cdot \dots \lambda_n$.
6. (5%) Apply "Cauchy-Schwarz Inequality" and prove \(\| \vec{u} +\vec{v}\| \leq \| \vec{u}\| +\| \vec{v}\|\)
7. Linear Transformation Problems:

(a) (5%) If \( L \) is a linear transformation mapping from \( R^n \) into \( R^m \), there is an \( m \) by \( n \) matrix \( A \) such that \( L(\vec{x}) = A\vec{x} \) for each \( \vec{x} \in R^n \). This is the matrix representation for a linear transformation. Prove that the \( j \)th column vector \( \vec{a}j \) of \( A \) is given by \( \vec{a}j = L(\vec{e}_j) \), for \( j = 1, 2, \dots, n \).
(b) (5%) Let \( L(\vec{x}) = (2\vec{x}1 - \vec{x}2 - \vec{x}3, \vec{x}1 + 2\vec{x}2 - \vec{x}3)^{\mathrm{T}} \) be the transformation from \( R^3 \) to \( R^2 \). Determine the standard matrix representation \( A \) of the above transformation and find \( L(\vec{x}) \) for \( \vec{x} = (1, 2, 3)^{\mathrm{T}} \).