No.2446 Exact Sequence
タグ : / 解いたユーザー数 17
作問者 : 👑
Problem Statement
You are given $3$ positive integers $L, M, N$, an $L \times M$ matrix $A$ with integer coefficients, and an $M \times N$ matrix $B$ with integer coefficients as input.
$(A,B)$ is called a good pair if, for every $M$-dimensional column vector $x$ with real coefficients, the following $2$ conditions are equivalent:
- $Ax$ is the zero vector.
- There exists an $N$-dimensional column vector $y$ with real coefficients satisfying $x = By$.
Determine whether $(A,B)$ is a good pair.
Background
Let $g$ denote the linear map $\mathbb{R}^M \to \mathbb{R}^L$ defined by left multiplication by $A$, and let $f$ denote the linear map $\mathbb{R}^N \to \mathbb{R}^M$ defined by left multiplication by $B$. In the field of homological algebra, the statement that $(A,B)$ is a good pair is expressed by saying that the sequence of linear maps
$\displaystyle \mathbb{R}^N \stackrel{f}{\to} \mathbb{R}^M \stackrel{g}{\to} \mathbb{R}^L $
is exact, or that it is an exact sequence. The concept of exact sequences is used extensively in the theory of modules in algebra, in geometry, and elsewhere, and is also widely treated in category theory; it is one of the fundamental tools of modern mathematics.
Input
Below, for a positive integer $i$ not exceeding the number of columns of a matrix $C$ and a positive integer $j$ not exceeding its number of rows, $C_{i,j}$ denotes the $(i,j)$ entry of $C$.
The input is given from standard input in $1 + L + M$ lines, in the following format.
- Line $1$ contains $L, M, N$, separated by single-byte spaces.
- For each positive integer $i$ not exceeding $L$, line $1 + i$ contains $A_{i,j}$ for each positive integer $j$ not exceeding $M$, in increasing order of $j$, separated by single-byte spaces.
- For each positive integer $j$ not exceeding $M$, line $1 + L + j$ contains $B_{j,k}$ for each positive integer $k$ not exceeding $N$, in increasing order of $k$, separated by single-byte spaces.
$L$ $M$ $N$
$A_{1,1}$ $\cdots$ $A_{1,M}$
$\vdots$
$A_{L,1}$ $\cdots$ $A_{L,M}$
$B_{1,1}$ $\cdots$ $B_{1,N}$
$\vdots$
$B_{M,1}$ $\cdots$ $B_{M,N}$
Constraints
The input satisfies the following constraints:
- $L, M , N$ are integers satisfying $1 \leq L, M, N$ and $LM, MN \leq 15$
- Each entry $a$ of $A , B$ is an integer satisfying $-6 \leq a \leq 6$
Output
Print Yes if $(A,B)$ is a good pair, and No if it is not.
Print a newline at the end.
Sample
Sample 1
Input
1 1 1 -2 3
Output
No
We have $A = (-2)$ and $B = (3)$. If we define the $1$-dimensional column vector $x$ with real coefficients as $(1)$, then $Ax = (-2 \cdot 1) = (-2)$ is not the zero vector, but if we define the $L = 1$-dimensional column vector $y$ with real coefficients as $(3^{-1})$, then $x = By$ holds.
Sample 2
Input
1 1 1 0 0
Output
No
We have $A = (0)$ and $B = (0)$. If we define the $1$-dimensional column vector $x$ with real coefficients as $(1)$, then $Ax = (0 \cdot 1) = (0)$ is the zero vector, but there exists no $L = 1$-dimensional column vector $y$ with real coefficients satisfying $x = By$.
Sample 3
Input
1 2 1 1 0 0 1
Output
Yes
$\displaystyle \begin{array}{rcl} \displaystyle A &\displaystyle = &\displaystyle \left( \begin{array}{cc} 1 & 0 \end{array} \right) \\ \displaystyle B &\displaystyle = &\displaystyle \left( \begin{array}{c} 0 \\ 1 \end{array} \right) \\ \end{array} $
are the given matrices. Let $x$ be a $2$-dimensional column vector $x$ with real coefficients, and using real numbers $x_0, x_1$, write
$\displaystyle x = \left( \begin{array}{c} x_0 \\ x_1 \end{array} \right) \\ $
Since $Ax = (1 \cdot x_0 + 0 \cdot x_1) = (x_0)$, a necessary and sufficient condition for $Ax$ to be the zero vector is $x_0 = 0$.
If $x_0 = 0$, then defining the $1$-dimensional column vector $y$ with real coefficients as $(x_1)$ gives $x = By$. Conversely, if there exists a $1$-dimensional column vector $y$ with real coefficients satisfying $x = By$, then writing $y = (y_0)$ using a real number $y_0$, we get
$\displaystyle \left( \begin{array}{c} x_0 \\ x_1 \end{array} \right) = x = By = \left( \begin{array}{c} 0 \\ 1 \end{array} \right) (y_0) = \left( \begin{array}{c} 0 \\ y_0 \end{array} \right) $
so comparing the $1$st component shows that $x_0 = 0$. From the above, $x_0 = 0$ is equivalent to the existence of a $1$-dimensional column vector $y$ with real coefficients satisfying $x = By$. That is, $(A,B)$ is a good pair.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。