დოჯსონის კონდენსაცია

მათემატიკაში დოჯსონის კონდენსაცია ან კონტრაქტორების მეთოდი ეწოდება კვადრატული მატრიცის დეტერმინანტის გამოთვლის ალგორითმს. მას თავისი გამომგონებლის, ჩარლზ ლუტვიჯ დოჯსონის სახელი მიენიჭა, რომელიც უფრო ცნობილია ფსევდონიმით ლუის კეროლი, როგორც ავტორი ნაწარმოებისა „ალისას თავგასავლები საოცრებათა ქვეყანაში“. დოჯსონმა აღნიშნული მეთოდი პირველად აღწერა 1866 წელს თავის ერთადერთ მეცნიერულ ნაშრომში. შემდგომში ეს მეთოდი შევიდა დოჯსონის მიერ დაწერილ სასწავლო წიგნში სათაურით: An Elementary Treatise on Determinants, with their application to simultaneous linear equations and algebraical geometry (ყვებიან, თითქოს დედოფალ ვიქტორიას ისე მოსწონებია „ ალისას თავგასავლები საოცრებათა ქვეყანაში“, რომ მოუთხოვია აუცილებლად მიეცათ წასაკითხად ლ. კეროლის ყველა ახალი ნაწარმოები და რომ მის გაკვირვებას საზღვარი არ ჰქონდა, როდესაც სულ მალე აღნიშნული სასწავლო წიგნი მიართვეს).

დოჯსონის კონდენსაციის ალგორითმი მდგომარეობს შემდგომში: თუ გვაქვს $n\times n$ მატრიცა $A$, მისი ელემენტებისგან გარკვეული წესით აიგება $(n-1)\times (n-1)$ მატრიცა $B$, ხოლო $A$ და $B$ მატრიცების ელემენტებისგან აიგება $(n-2)\times (n-2)$ მატრიცა $C$, და ა.შ. პროცესი დასრულება $1\times 1$ მატრიცის აგებით, რომელის ერთადერთი ელემენტიც იქნება $A$ მატრიცის დეტერმინანტი.

ზოგადი მეთოდი

ახლა უფრო დაწვრილებით აღვწეროთ ეს ალგორითმი:

1. ვთქვათ მოცემული გვაქვს $n$-ური რიგის $A=(a_{ij})_{i,j=1}^{n}$ მატრიცა, რომლის შიგა ელემენტებიც განსხვავებულია ნულისგან, ანუ $a_{i,j}\not =0$ $(i,j\not =1,n)$ . საწინააღმდეგო შემთხვევაში ელემენტარული გარდაქმნებით, დეტერმინანტის მნიშვნელობის შეუცვლელად, გადავალთ ახალ მატრიცაზე რომლის შიგა ელებენტებიც ნულისგან განსხვავებული იქნება. მაგალითად, რომელიმე სტრიქონს გავამრავლებთ არანულოვან რიცხვზე და მივუმატებთ ჩვენთვის სასურველ სხვა სტრიქონს.
2. $A$ მატრიცის ელემენტებისაგან შევადგენთ $n-1$ რიგის $B=(b_{i,j})_{i,j=1}^{n-1}$მატრიცას, შემდეგი წესით $b_{i,j}={\begin{vmatrix}a_{i,j}&a_{i,j+1}\\a_{i+1,j}&a_{i+1,j+1}\end{vmatrix}}\;\;(i,j={\overline {1,n-1}}).$
3. ახლა $A=(a_{i,j})_{i,j=1}^{n}$ და $B=(b_{i,j})_{i,j=1}^{n-1}$ მატრიცების ელემენტებისგან შევადგენთ ახალ $n-2$ რიგის $C=(c_{i,j})_{i,j}^{n-2}$ მატრიცას შემდეგი წესით $c_{i,j}={\begin{vmatrix}b_{i,j}&b_{i,j+1}\\b_{i+1,j}&b_{i+1,j+1}\end{vmatrix}}/a_{i+1,j+1}\;\;(i,j={\overline {1,n-2}})$ .
4. თუ $b_{i,j}\not =0(i,j\not =1,n-1)$, შემოვიღებთ აღნიშვნებს $A:=B,\;\;B:=C$ და აღნიშნულ ალგორითმს იმდენჯერ გავიმეორებთ სანამ არ მივიღებთ $1\times 1$ მატრიცას, რომლის ერთადერთი ელემენტიც აღმოჩნდება $\det {(A)}$.

მაგალითი

ნულების გარეშე

განვიხილოთ მატრიცა

${\begin{bmatrix}-2&-1&-1&-4\\-1&-2&-1&-6\\-1&-1&2&4\\2&1&-3&-8\end{bmatrix}},$

რომლის ყველა შიგა ელემენტიც არანულოვანია და გამოვთვალოთ $\det(A)$.

ამისათვის ჯერ $A$ მატრიცის მეორე რიგის მინორებისგან შევადგინოთ მატრიცა

${\begin{bmatrix}{\begin{vmatrix}-2&-1\\-1&-2\end{vmatrix}}&{\begin{vmatrix}-1&-1\\-2&-1\end{vmatrix}}&{\begin{vmatrix}-1&-4\\-1&-6\end{vmatrix}}\\\\{\begin{vmatrix}-1&-2\\-1&-1\end{vmatrix}}&{\begin{vmatrix}-2&-1\\-1&2\end{vmatrix}}&{\begin{vmatrix}-1&-6\\2&4\end{vmatrix}}\\\\{\begin{vmatrix}-1&-1\\2&1\end{vmatrix}}&{\begin{vmatrix}-1&2\\1&-3\end{vmatrix}}&{\begin{vmatrix}2&4\\-3&-8\end{vmatrix}}\end{bmatrix}}={\begin{bmatrix}3&-1&2\\-1&-5&8\\1&1&-4\end{bmatrix}}.$

ამ უკანასკნელისა და $A$ მატრიცის შიგა ელემენტებისგან 3. პუნქტის მიხედვით შევადგინოთ მატრიცა

${\begin{bmatrix}{\begin{vmatrix}3&-1\\-1&-5\end{vmatrix}}:(-2)&{\begin{vmatrix}-1&2\\-5&8\end{vmatrix}}:(-1)\\\\{\begin{vmatrix}-1&-5\\1&1\end{vmatrix}}:(-1)&{\begin{vmatrix}-5&8\\1&-4\end{vmatrix}}:2\end{bmatrix}}={\begin{bmatrix}8&-2\\-4&6\end{bmatrix}}.$

ბოლოს ისევ 3. პუნქტის მიხედვით მატრიცებისგან

${\begin{bmatrix}3&-1&2\\-1&-5&8\\1&1&-4\end{bmatrix}}\;\;{\text{დ ა}}\;\;{\begin{bmatrix}8&-2\\-4&6\end{bmatrix}},$

შევადგინოთ მატრიცა

$C={\begin{bmatrix}{\begin{vmatrix}8&-2\\-4&6\end{vmatrix}}:(-5)&\end{bmatrix}}=[-8],$

და მაშინ $\det(A)=-8$.

ნულებით

აღნიშნული ალგორითმი ჩიხში შეგვიყვანს თუ რომელიმე ეტაპზე მივიღეთ მატრიცას, რომლის შიგა ელემენტებს შორისაც არის ნულები, რადგან ასეთ შემთხვევაში პროცესის გასაგრძელებლად 3. პუნქტის ძალით ნულზე გაყოფა მოგვიწევდა. ასეთია ვთქვათ შემდეგი მატრიცი

${\begin{bmatrix}2&-1&2&1&-3\\1&2&1&-1&2\\1&-1&-2&-1&-1\\2&1&-1&-2&-1\\1&-2&-1&-1&2\end{bmatrix}}\to {\begin{bmatrix}5&-5&-3&-1\\-3&-3&-3&3\\3&3&3&-1\\-5&-3&-1&-5\end{bmatrix}}\to {\begin{bmatrix}-15&6&12\\0&0&6\\6&-6&8\end{bmatrix}}.$

ამიტომ ასეთ შემთხვევაში თავდაპირველ მატრიცას სჭირდება ელემენტარული გარდაქმნებით (რათა დეტერმინანტის მნიშვნელობა არ შეიცვალოს) ისეთ სახეზე მიყვანა, რომ ნულოვანი შიგა წევრები არცერთ ეტაპზე არ გავიჩნდეს და მხოლოდ ამის შემდეგ შიძლება ალგორითმის გამოყენება. მაგალითად

${\begin{bmatrix}1&2&1&-1&2\\1&-1&-2&-1&-1\\2&1&-1&-2&-1\\1&-2&-1&-1&2\\2&-1&2&1&-3\end{bmatrix}}\to {\begin{bmatrix}-3&-3&-3&3\\3&3&3&-1\\-5&-3&-1&-5\\3&-5&1&1\end{bmatrix}}\to {\begin{bmatrix}0&0&6\\6&-6&8\\-17&8&-4\end{bmatrix}}\to {\begin{bmatrix}0&12\\18&40\end{bmatrix}}\to {\begin{bmatrix}36\end{bmatrix}}.$

დოჯსონის კონდენსაციის ალგორითმის დამტკიცება და გამოყენებები

დოჯსონის კონდენსაციის ალგორითმი მტკიცდება დესნანო-იაკობის (Desnanot – Jacobi (1841)) ან უფრო ზოგადი სილვესტერის დეტერმინანტის იგივეობაზე (1851) დაყრდნობით. დესნანო – იაკობის იგივეობა ეწოდება ტოლობას

$\det(M)\cdot \det(M_{1,n}^{1,n})=\det(M_{1}^{1})\cdot \det(M_{n}^{n})-\det(M_{1}^{n})\cdot \det(M_{n}^{1})$,

სადაც $M=(m_{i,j})_{i,j=1}^{n}$ არის კვადრატული მატრიცა, $M_{i}^{j}$ არის მატრიცა, რომელიც მიიღება $M$ მატრიციდან $i$-ური სტრიქონისა და $j$-ური სვეტის ამოშლით, ხოლო $M_{i,j}^{p,q}$ არის მატრიცა, რომელიც მიიღბა $M$ მატრიციდან $i$-ური $j$-ური სტრიქონებისა და $p$-ური $q$-ური სვეტების ამოშლით.

კონდენსაციის ალგორითმის დამტკიცებით დაინტერესებულ მკითხველს ვთავაზობთ გაეცნოს სტატიას და იქ მითითებულ ლიტერატურას.

დოჯსონის კონდენსაციის საინტერესო გამოყენება წრფივ ალგებრულ განტოლებათა სისტემების კრამერის წესით ამოხსნისას მოყვანილია ნაშრომში .