선형대수학에서 Cramer's rule은 알 수 없는 수만큼 많은 방정식을 갖는 선형 방정식의 해에 대한 명시적인 공식으로, 시스템이 고유한 해를 가질 때마다 유효합니다. 한 열을 방정식의 우변 열 벡터로 대체하여 (제곱) 계수 행렬의 행렬식과 그 행렬식의 행렬식으로 해를 표현합니다. 1750년에 임의의 수의 미지수에 대한 규칙을 발표한 가브리엘 크레이머의 이름을 [1][2]따서 명명되었지만 콜린 매클로린도 1748년에 규칙의 특별한 사례를 발표했고 [3]아마도 1729년에 이 규칙을 알고 있었을 것입니다.[4][5][6]
순진한 방법으로 구현된 크레이머의 법칙은 2개 또는 3개 이상의 방정식 체계에 계산상 비효율적입니다.[7]n개의 미지수에 있는 n개의 방정식의 경우 n+1 행렬식의 계산이 필요한 반면, 가우시안 소거는 단일 행렬식의 계산과 동일한 계산 복잡도로 결과를 생성합니다.[8][9][verification needed] Cramer의 규칙은 2×2 시스템에서도 수치적으로 불안정할 수 있습니다.[10] 그러나 최근 Cramer의 규칙이 가우시안 제거와 동일한 복잡성으로 구현될 수 있음이 나타났습니다([11][12]동일한 순열 행렬을 적용할 때 지속적으로 두 배의 산술 연산이 필요하고 동일한 수치 안정성이 있음).
행렬 곱셈 형태로 표현되는 n개의 미지수에 대한 n개의 선형 방정식 체계를 다음과 같이 생각해 보자.
여기서 n× n 행렬 A는 0이 아닌 행렬식을 가지며, x =(1, …, x n) T {\displaystyle \mathbf {x} = (x_{1},\ldots,x_{n})^{\mathsf {T}}는 변수의 열 벡터입니다. 그러면 이 정리는 이 경우 시스템이 고유한 해를 가지며, 미지수에 대한 개별 값은 다음과 같이 주어집니다.
여기서 n× n 행렬 A는 0이 아닌 행렬식을 가지며, X, B는 n× m 행렬입니다. Given sequences and , let be the k × k submatrix of X with rows in :=(i_j 1, j k) {\displaystyle :=(j_{1},\ldots,j_{k)}의 열을 표시합니다. AB (I,J) {\displaystyle A_{B}(I,}은 모든 1 {\displaystyle s 1,\ldots,k}에 대하여 의 is 열을 의 j 열로 치환하여 형성한 n 행렬입니다. 그러면
= displaystyle k = 1}의 경우, 이는 일반적인 Cramer's rule로 축소됩니다.
이 규칙은 실수뿐만 아니라 어떤 분야에서든 계수와 미지수를 가진 방정식 체계에 적용됩니다.
증명
Cramer's rule에 대한 증명은 행렬식의 다음 속성을 사용합니다: 주어진 열에 대한 선형성과 두 열이 같을 때마다 행렬식이 0이라는 사실. 이 속성은 두 열을 바꾸면 행렬식의 부호가 뒤집힌다는 것을 의미합니다.
열의 인덱스 j를 고정하고 다른 열의 항목이 고정된 값을 갖는다고 생각합니다. 이렇게 하면 행렬식이 j번째 열의 항목에 대한 함수가 됩니다. 이 열에 대한 선형성은 이 함수가 다음과 같은 형태를 가짐을 의미합니다.
는 열 j에 없는 A의 항목에 의존하는 계수입니다. 그래서, 한 명은.
(라플라스 확장은 를 계산하는 공식을 제공하지만 여기서는 이들 표현이 중요하지 않습니다.)
함수 를 A의 다른 열 k에 적용하면 열 j를 열 k의 복사본으로 대체하여 A에서 얻은 행렬식이 되므로 결과 행렬식은 0이 됩니다(두 개의 동일한 열인 경우).
이제 n개의 미지수 의 n개의 선형 방정식 체계를 생각해 보자 계수 행렬은 A이고 det(A)는 0이 아니라고 가정합니다.
만약 어떤 사람이1,j 첫 번째 방정식의 C배에 두2,j 번째 방정식의 C배를 더해서 이 방정식들을 결합한다면, 그n,j 결과 x의k 계수는 매 k에 대해 다음과 같이 됩니다.
따라서 가 되는 의 계수를 제외한 모든 계수는 0이 됩니다마찬가지로 상수 계수는 ( 1 b 가 되며, 결과 방정식은 다음과 같습니다.
값은 x {\x_{의 값을 다음과 같이 제공합니다.
구성상 분자는 열 j를 b로 대체하여 A에서 얻은 행렬의 행렬식이므로, 우리는 해의 필요조건으로 Cramer's rule이라는 표현을 얻습니다.
미지수에 대한 이러한 값이 해를 형성한다는 것을 증명해야 합니다. 행으로 의 계수를 가지는 n × n 행렬을 M이라 하자. = 1…, ndisplaystyle j = 1,\ldots, n}에 대하여 (이는 A에 대한 인접 행렬입니다. 행렬식으로 표현하면, 우리는 다음을 증명해야 합니다.
여기서 adj(A)는 인접 행렬, det(A)는 행렬식, I는 항등 행렬입니다. det(A)가 0이 아닌 경우 A의 역행렬은
이것은 det(A) ≠ 0인 경우 A의 역에 대한 공식을 제공합니다. 실제로 이 공식은 det(A)가 단위인 경우F가 교환환일 때마다 작동합니다. det(A)가 단위가 아닌 경우, A는 링 위에서 가역적이지 않습니다(F의 일부 비단위 요소가 가역적일 수 있는 더 큰 링 위에서 가역적일 수 있습니다).
적용들
소형 시스템에 대한 명시적 공식
선형 시스템을 고려합니다.
행렬 형식에서
ab12 -ba가12 0이 아니라고 가정합니다. 그런 다음, 행렬식의 도움을 받아x와 y는 Cramer의 법칙으로 구할 수 있습니다.
특히, Cramer의 법칙은 리만 다양체의 발산 연산자가 좌표 변화에 대해 불변하다는 것을 증명하는 데 사용될 수 있습니다. 우리는 크리스토펠 상징의 역할을 억제하면서 직접적인 증거를 제시합니다. Let be a Riemannian manifold equipped with local coordinates. Let be a vector field. 우리는 요약 협약을 내내 사용합니다.
정리.
A의 발산
좌표의 변화에 따라 불변입니다.
증명
↦(¯ 1 …, x ¯ }, x^{2ldots,{\bar {x}}^{n})}를 비특이 자코비안과의 좌표 변환이라 하자. Then the classical transformation laws imply that where 마찬가지로, kd x d x k g i j x i가 d x j {\display gg_{}\, ^{m}\otimes dx^{k}{\bar {g}_{ij}\,d{\bar {x}}^{i}\otimes d{\bar {x}}^{j}, ¯ i = ∂ x m ∂ x ¯ i ∂ x k ¯ j m k {\displaystyle {\bar {g}_{ij}=\,{\frac {\partial x^{m}}{\partial {\bar {x}}^{i}}{\frac {\partial x^{k}}{\partial {\x}}}{\bar {x}}^{j}}g_{mk}}. 이 변환 법칙을 행렬로 쓰면 ¯ =∂ x ¯ x ¯) (∂ x ∂) {\displaystyle {\bar{g}}=\left ({\frac {\partial x}{\bar {x}}}\right)^{\text{right)}, x x ) 2 det g {\displaystyle {\bar {g}}\left(\det \left \frac {\ x}}{\bar {x}}\right)^{2}\det g}.
이제 컴퓨터 한 대.
값이 1 ¯ ∂ ∂ ¯ (¯ k det g ¯ {\ {1{\ {\bar x}^{{{\det {\bar {g}}\right)}와 같음을 보이기 위해서는 다음과 같은 값을 나타내는 것이 필요하고 충분합니다.
에 해당하는 것.
좌측에서 차별화를 수행하면 다음과 같은 이점을 얻을 수 있습니다.
여기서 은 i 과 j {\ 열을 ∂∂x ¯) {\\left({\frac {\x}{\ {x}}}\에서 얻은 행렬을 나타냅니다. 하지만 크레이머의 규칙에 따르면
는 행렬∂ ¯ ∂ x )의(번째 항목입니다. displaystyle \frac {\bar {\x}}{\partial x}}{\partial x}\right)}. 따라서
증명을 완료하는 중입니다.
함축적으로 도함수를 계산하는 것
Consider the two equations and . When u and v are independent variables, we can define and
∂∂ udisplaystyle {\dfrac {\partial x}{\partial u}}에 대한 식은 Cramer's rule을 적용하여 구할 수 있습니다.
∂∂u {\dfrac {\ xpartial u}}의 계산
먼저 F, G, x, y의 1차 도함수를 계산합니다.
dx, dy를 dF와 dG로 바꾸면 다음과 같습니다.
u, v는 둘 다 독립적이므로 du, dv의 계수는 0이어야 합니다. 따라서 계수에 대한 식을 다음과 같이 쓸 수 있습니다.
∂∂ v, ∂ y ∂ u, ∂ y ∂ v에 대해서도 유사한 공식을 유도할 수 있습니다. {\displaystyle {\frac {\partial x}{\partial v}}, {\frac {\partial u}, {\frac {\partial y}, {\partial v}}.
정수 프로그래밍
Cramer의 규칙을 사용하여 제약 행렬이 완전히 단일 모듈이고 우변이 정수인 정수 프로그래밍 문제가 정수 기본 솔루션을 가지고 있음을 증명할 수 있습니다. 이를 통해 정수 프로그램을 훨씬 쉽게 해결할 수 있습니다.
상미분방정식
Cramer's rule은 매개변수의 변동 방법에 의해 비균질 선형 미분 방정식에 대한 일반적인 해를 도출하는 데 사용됩니다.
기하학적 해석
크레이머의 법칙은 기하학적 해석을 가지고 있는데, 이는 단순히 기하학적 성질에 대한 통찰력을 제공하거나 증명으로도 간주될 수 있습니다. 이러한 기하학적 논증은 일반적으로 작동하며 여기에 제시된 두 개의 미지수가 있는 두 개의 방정식의 경우에만 작동하지 않습니다.
주어진 방정식 체계
벡터 사이의 방정식으로 간주될 수 있습니다.
및(에 의해 결정된 평행사변형의 면적은 방정식 체계의 행렬식에 의해 제공됩니다.
일반적으로 변수와 방정식이 더 많을 때 길이가 n인 벡터의 행렬식은 n차원 유클리드 공간에서 해당 벡터에 의해 결정된 평행육면체의 부피를 제공합니다.
그러므로, the area of the parallelogram determined by and has to be times the area of the first one since one of the sides has been multiplied 이 요인에 의해서 이제 이 마지막 평행사변형은 Cavalieri의 원리에 의해( 1 = (a a + 2 (a 12 a 22) {\displaystyle {\binom {b_{1}} {b_{2}} = x_{1} {a_{11}} {a_{21}} + x_{2}와(
이 마지막 평행사변형과 두 번째 평행사변형의 넓이를 같게 하면 다음과 같은 식을 얻을 수 있습니다.
크레이머의 법칙이 따르는 것입니다.
기타 증명
추상적 선형대수에 의한 증명
위의 증명을 추상적인 언어로 다시 진술한 것입니다.
지도 =(1, x ) ↦ 1 det A (detA 1), …, det (A n), {\displaystyle \mathbf {x} = (x_{1},\ldots,x_{n})\map to {\frac {1},\det A}\left(\det(A_{1}),\ldots,\det(A_{n})\right),여기서는 Cramer's rule과 같이 i번째 열에 가 치환된 행렬 A입니다. 모든 열의 행렬식 선형성 때문에 이 지도는 선형입니다. Observe that it sends the th column of to the th basis vector (with 1 in the th place), 열이 반복되는 행렬의 행렬식은 0이기 때문입니다. 따라서 우리는 열 의A {\ A의 역수와 일치하는 선형 맵을 가지고 있습니다. 따라서 열 공간의 범위에서- 1 A과 일치합니다. 는 가역이므로 열 벡터는 에 걸쳐 있으므로 우리의 지도는 A 의 역이다 크레이머의 법칙은 다음과 같습니다.
짧은 증명
이 행렬의 행렬식이라는 것을 알면 Cramer의 법칙에 대한 간단한 증명을 얻을 수 있습니다.
반면에, 우리의 원래 행렬 A가 가역적이라고 가정하면, 이 행렬 은 열 - 1 - 1 A- _서 은 행렬 A의 n번째 열입니다. 행렬 에는 b 2 _ _이있으므로 = - 1 {\displaystyle X_{1} = A^{-1}A_{1}}가 있습니다. 따라서, 두 행렬의 곱의 행렬식이 행렬식의 곱이라는 것을 사용함으로써, 우리는
다른 의 증명도 유사합니다.
일관성이 없고 불확실한 경우
방정식 체계는 해가 없을 때 일관성이 없다고 하고 해가 둘 이상일 때는 불확정이라고 합니다. 선형 방정식의 경우, 불확정 시스템은 임의의 값을 취할 수 있는 하나 이상의 매개 변수로 표현될 수 있기 때문에 무한히 많은 해를 가질 것입니다.
크레이머의 법칙은 계수 행렬식이 0이 아닌 경우에 적용됩니다. 2×2의 경우 계수 행렬식이 0이면 분자 행렬식이 0이 아니면 시스템이 호환되지 않거나 분자 행렬식이 0이면 불확실합니다.
3×3 이상의 시스템의 경우 계수 행렬식이 0일 때 유일하게 말할 수 있는 것은 분자 행렬식 중 하나가 0이 아닌 경우 시스템이 일관되지 않아야 한다는 것입니다. 그러나 모든 행렬식이 0이라는 것이 시스템이 불확실하다는 것을 의미하지는 않습니다. 모든 행렬식이 사라지지만(equal 0) 시스템이 여전히 호환되지 않는 간단한 예로는 3×3 시스템 x+y+z=1, x+y+z=2, x+y+z=3이 있습니다.
^G.I.Malaschonok (1983). "Solution of a System of Linear Equations in an Integral Ring". USSR J. Of Comput. Math. And Math. Phys. 23: 1497–1500. arXiv:1711.09452.