본문 바로가기

선형대수학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, \dots, 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} - 4 X + 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 \leq N \leq 500

1 \leq M \leq 5000

를 만족한다. www.acmicpc.net 선형대수학 D3 문제치고는 굉장히 어려웠다. 구현이 쉬워서 난이도가 약간 깎인 듯싶다. 일단 결론은

m \leq n

\sqrt{m n}

이 자연수라는 조건이 필요충분조건이다. () 방향 증명은 어렵다. 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{matrix} A & A^{2} \\ A^{3} & A^{4} \end{matrix}) = 0

임을 보여라. (단,

A

의 모든 성분은 실수이다.) Sol) 주어진 행렬을 다음과 같이 다시 쓸 수 있다.

(\begin{matrix} A & A^{2} \\ A^{3} & A^{4} \end{matrix}) = (\begin{matrix} I \\ A^{2} \end{matrix}) (\begin{matrix} A & A^{2} \end{matrix})

따라서 주어진 행렬은

2 n \times 2 n

행렬이지만 그 rank가

n

이하이므로 행렬식이

0

이다. 2022. 9. 14.

[대학생 수학경시대회] 2021년 제2분야 7번 7. 실수

a, b

에 대하여 행렬

A

를 다음과 같이 정의하자.

A = (\begin{matrix} a & 1 & 1 & 1 \\ 1 & b & 1 & 1 \\ 1 & 1 & a & 1 \\ 1 & 1 & 1 & b \end{matrix})

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

\frac{\partial}{\partial x_{i j}} X = E_{i j}, \frac{\partial}{\partial x_{i j}} A = O

이다. 여기서

E_{i j}

는 (i, j)-성분만 1이고 나머지 성분은 0인 행렬이고,

O

는 영행렬이다. 따라서 곱의 미분법에 의해

O = \frac{\partial}{\partial x_{i j}} I = \frac{\partial}{\partial x_{i j}} X Y = E_{i j} Y + X \frac{\partial}{\partial x_{i j}} 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 R^{4}

v_{1}, v_{2}, v_{3}, v_{4}

W

에 정사영하여 얻은 벡터들 가운데 적어도 하나는 길이가 1이 아님을 보여라. Sol) 일반성을 잃지 않고

v_{1} = 2 e_{1}, v_{2} = 3 e_{2}, v_{3} = 4 e_{3}, v_{4} = 5 e_{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

A

. Let us denote element in

i

j

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.

이전 1 다음

티스토리툴바