본문 바로가기

선형대수학11

[백준 21117] Number of Colorful Matchings [Ruby III] https://www.acmicpc.net/problem/21117 21117번: Number of Colorful Matchings Output $n + 1$ lines containing your answers for $k = 0, 1, 2, \ldots, n$ respectively. Remember that you only need to output the answer modulo $2$. www.acmicpc.net 알아두어야 할 배경지식이 몇 개 있다. 자세한 사항은 https://en.wikipedia.org/wiki/Permanent_(mathematics) 여기를 참고했다. 1. 이분 그래프 G의 adjoint matrix는 \( \begin{bmatrix} O & A \\ A^T & O.. 2023. 2. 6.
[백준 3904] The Teacher's Side of Math (Diamond IV) https://www.acmicpc.net/problem/3904 3904번: The Teacher's Side of Math One of the tasks students routinely carry out in their mathematics classes is to solve a polynomial equation. It is, given a polynomial, say \(X^2 − 4X + 1\), to find its roots \((2\pm \sqrt{3})\). If the students’ task is to find the roots of a giv www.acmicpc.net \( \sqrt[m]{a} + \sqrt[n]{b} \)를 근으로 갖는 정수 계수 mn차 다항식을 찾는 문제.. 2023. 1. 12.
[백준 16224] Path Equality (Diamond III) https://www.acmicpc.net/problem/16224 16224번: Path Equality $N$, $M$이 한 줄에 차례대로 입력된다. 입력은 $1 \le N \le 500$, $1 \le M \le 5000$를 만족한다. www.acmicpc.net 선형대수학 D3 문제치고는 굉장히 어려웠다. 구현이 쉬워서 난이도가 약간 깎인 듯싶다. 일단 결론은 \( m \leq n \)이고 \( \sqrt{mn} \)이 자연수라는 조건이 필요충분조건이다. () 방향 증명은 어렵다. n = 9이고 m = 1인 경우로 사례연구를 해 보자. tr(A) = 3이므로 9개의 노드 중 3개는 자기 자신을 향하는 loop를 갖고, 나머지 6개는 그렇지 않다. 일단 자기 자신을 향하는 loop를 갖는 3개의 노.. 2023. 1. 11.
[C++] class Matrix 구현 내가 class Matrix를 아직도 이 블로그에 안 올려놨다니,,, 덧셈, 뺄셈, 곱셈, 스칼라배, 기본행/기본열 연산 등의 기능을 지원한다. 근데 뭐 이거 구현한다고 250줄을 잡아먹냐. template class Matrix { private: T** p; unsigned int n; // size public: explicit Matrix(int _n) : n(_n) { this->init(); } ~Matrix() { if (p) { for (int i = 0; i init(); for (int i = 0; i < n; ++i) { fo.. 2022. 9. 24.
[대학생 수학경시대회] 2011년 제2분야 2번 2. 임의의 \( n \times n \) 행렬 \( A \)에 대하여, $$ \det \begin{pmatrix} A & A^2 \\ A^3 & A^4 \end{pmatrix} = 0 $$ 임을 보여라. (단, \( A \)의 모든 성분은 실수이다.) Sol) 주어진 행렬을 다음과 같이 다시 쓸 수 있다. $$ \begin{pmatrix} A & A^2 \\ A^3 & A^4 \end{pmatrix} = \begin{pmatrix} I \\ A^2 \end{pmatrix} \begin{pmatrix} A & A^2 \end{pmatrix} $$ 따라서 주어진 행렬은 \( 2n \times 2n \) 행렬이지만 그 rank가 \( n \) 이하이므로 행렬식이 \( 0 \)이다. 2022. 9. 14.
[대학생 수학경시대회] 2021년 제2분야 7번 7. 실수 \(a, b\)에 대하여 행렬 \(A\)를 다음과 같이 정의하자. $$ A = \begin{pmatrix} a & 1 & 1 & 1 \\ 1 & b & 1 & 1 \\ 1 & 1 & a & 1 \\ 1 & 1 & 1 & b \end{pmatrix} $$ 이때 행렬 \(A\)가 양의 정부호(positive definite)일 필요충분조건은 \(a > 1\)이고 \(b > 1\)임을 보여라. Sol) \( (\Leftarrow) \) 행렬 \(J\)를 모든 성분이 \(1\)인 \(4 \times 4\) 행렬이라 하고, 대각행렬 \( D \)를 \( D = A - J \)라 하자. 그러면 \( D \)는 모든 대각성분이 양수인 대각행렬이므로 자명히 양의 정부호이고, 행렬 \(J\)는 대각화하여 $$.. 2022. 9. 2.
[대학생 수학경시대회] 2015년 제2분야 8번 임의의 i, j에 대해, 행렬 \( X \)와, \( X \)와 관련 없는 임의의 행렬 \( A \)에 대해 $$ {\partial \over \partial x_{ij}} X = E_{ij}, {\partial \over \partial x_{ij}} A = O $$ 이다. 여기서 \( E_{ij} \)는 (i, j)-성분만 1이고 나머지 성분은 0인 행렬이고, \( O \)는 영행렬이다. 따라서 곱의 미분법에 의해 $$ O = {\partial \over \partial x_{ij}} I = {\partial \over \partial x_{ij}} XY = E_{ij} Y + X {\partial \over \partial x_{ij}} Y $$ 로부터 $$ {\partial \over \parti.. 2022. 8. 29.
[대학생 수학경시대회] 2017년 제1분야 6번 주어진 조건만으로 생각보다 A에 대해 많은 것을 알 수 있는 문제입니다... 2022. 8. 29.
[대학생 수학경시대회] 2019년 제2분야 7번 7. 벡터 \( v_1, v_2, v_3, v_4 \)는 길이가 각각 2, 3, 4, 5이며 서로 수직이다. 임의의 2차원 부분공간 \( W \subset \mathbb{R}^4 \)에 대하여 \( v_1, v_2, v_3, v_4 \)를 \( W \)에 정사영하여 얻은 벡터들 가운데 적어도 하나는 길이가 1이 아님을 보여라. Sol) 일반성을 잃지 않고 \( v_1 = 2e_1, v_2 = 3e_2, v_3 = 4e_3, v_4 = 5e_4 \)라 하자. 그리고 선형사상 T를 Tv = (v의 W 위로의 정사영)으로 잡는다. 이제 네 정사영의 길이가 모두 1이라 가정하면 $$ \left\langle e_1, Te_1 \right\rangle = {1 \over 4}, \left\langle e_2, Te.. 2022. 8. 28.
[대학생 수학경시대회] 2021년 제2분야 6번 대한수학회에서 공식 제공하는 대학생 수학경시대회의 해설은 깔끔한 풀이보다는 색다른 풀이를 선호하는 경우가 많다. 그래서 여러 가지 방법으로 풀 수 있는 문제들에 대해서는 여러 풀이를 알아두는 것이 좋다. '행렬의 고유벡터는 그 행렬을 설명하는 특성 중 하나다'를 잘 나타내주는 문제라고 생각한다. 2022. 8. 28.
[백준 18542] Permutant (Ruby III) 풀이 https://www.acmicpc.net/problem/18542 18542번: Permutant Consider an \(n \times n\) matrix \(A\). Let us denote element in \(i\)-th row and \(j\)-th column as \(A_j^{(i)}\). You are given a sequence \(a_1, \dots , a_n\) and a permutation \(π_1, \dots , π_n\) such that the first row is formed by sequence \(a_k www.acmicpc.net 먼저 주어진 Permutation는 Linear Transform의 일종임을 파악해야 한다. 예를 들어, Permutation {.. 2022. 8. 4.

티스토리툴바