Кіріспе
Матрицаның қалыпты түріМатематикада Смиттің қалыпты түрі (кейде SNF деп қысқартылады) – кез келген матрица (квадрат болуы міндетті емес) үшін, негізгі идеалдық доменге (PID) жататын нормальды форма. Смиттің қалыпты түріндегі матрица диагональды болады және бастапқы матрицаны сол және оң жағынан кері квадрат матрицаларға көбейту арқылы алуға болады. Атап айтқанда, бүтін сандар PID болып табылады, сондықтан кез келген бүтін сандық матрицаның Смиттің қалыпты түрін есептеуге болады. Смиттің қалыпты түрі PID-дегі шекті жасалған модульдермен жұмыс істеу үшін, әсіресе бос модульдің бөлігінің құрылымын анықтау үшін өте пайдалы. Ол ирланд математигі Генри Джон Стивен Смиттің құрметіне аталған.
Анықтама
Негізгі идеалдық домендегі нөлдік емес матрица болсын. Коэффициенттері сақинада болатын инвертирленетін және матрицалары бар, олардың көбейтіндісі келесідей:
and the diagonal elements satisfy for all This is the Smith normal form of the matrix The elements are unique up to multiplication by a unit and are called the elementary divisors, invariants, or invariant factors. They can be computed (up to multiplication by a unit) as
where (called i th determinant divisor) equals the greatest common divisor of the determinants of all minors of the matrix and
Example : For a matrix, with and .
және диагональдық элементтері барлық үшін орындалады. Бұл матрицаның Смит нормалық түрі. Элементтер бірлікке көбейгенге дейін бірегей және элементар бөлгіштер, инварианттар немесе инвариантты факторлар деп аталады. Оларды (бірлікке көбейгенге дейін) мысылы, келесідей есептеуге болады:
and the diagonal elements satisfy for all This is the Smith normal form of the matrix The elements are unique up to multiplication by a unit and are called the elementary divisors, invariants, or invariant factors. They can be computed (up to multiplication by a unit) as
where (called i th determinant divisor) equals the greatest common divisor of the determinants of all minors of the matrix and
Example : For a matrix, with and .
мұнда (i-ші детерминантты бөлгіш деп аталады) матрицаның барлық i-реттік минорларының ең үлкен ортақ бөлгішіне тең және.
and the diagonal elements satisfy for all This is the Smith normal form of the matrix The elements are unique up to multiplication by a unit and are called the elementary divisors, invariants, or invariant factors. They can be computed (up to multiplication by a unit) as
where (called i th determinant divisor) equals the greatest common divisor of the determinants of all minors of the matrix and
Example : For a matrix, with and .
Мысал: матрица үшін, және .
and the diagonal elements satisfy for all This is the Smith normal form of the matrix The elements are unique up to multiplication by a unit and are called the elementary divisors, invariants, or invariant factors. They can be computed (up to multiplication by a unit) as
where (called i th determinant divisor) equals the greatest common divisor of the determinants of all minors of the matrix and
Example : For a matrix, with and .
Алгоритм
Бірінші мақсат – өзгеше квадраттық матрицаларды табу және олардың көбейтіндісі диагональды болуын қамтамасыз ету. Бұл алгоритмнің ең қиын бөлігі. Диагональдық түріне қол жеткізгеннен кейін, матрицаны Смит нормальды түріне келтіру салыстырмалы түрде оңай болады. Көбірек абстракцияласақ, мақсат – (рангтың бос модулі) мен (рангтың бос модулі) арасындағы бейнелеу ретінде қарастырғанда, диагональ матрицаның қарапайым түріне ие изоморфизмдердің бар екенін көрсету. және матрицаларын тиісті өлшемдегі бірлік матрицалардан бастап табуға болады, және алгоритмде қатар операциясы орындалған сайын, сәйкес баған операциясы арқылы оларды өзгертуге болады (мысалы, егер қатар , қатарға қосылса, онда өнім инвариантын сақтау үшін бағаннан алынуы керек), және орындалған әрбір баған операциясы үшін де осылай жасау керек. Қатар операциялары сол жақтан көбейту, ал баған операциялары оң жақтан көбейту болғандықтан, бұл инвариантты сақтайды, мұнда – ағымдағы мәндерді, ал – бастапқы матрицаны білдіреді; соңында осы инварианттағы матрицалар диагональды болады. Тек өзгеше қатар және баған операциялары ғана орындалады, бұл және матрицаларының өзгеше болып қалатынын қамтамасыз етеді. үшін , (олар бар және бірегей, өйткені кез келген PID сонымен қатар бірегей жіктеу домені) санын жазыңыз. Атап айтқанда, сонымен қатар Безу домені, сондықтан ол ең үлкен ортақ бөлгіш домені және кез келген екі элементтің ең үлкен ортақ бөлгіші Безу теңдігін қанағаттандырады. Матрицаны Смит нормальды түріне келтіру үшін келесі әдісті қайталап қолдануға болады, мұнда 1-ден .
Бірінші қадам: Півотты таңдау
Ең нөлдік емес элементі бар ең кіші бағана индексін таңдаңыз, іздеуді бағана индексінен бастап. Егер бізді қанағаттандырса, онда бұл қадам аяқталады. Әйтпесе, болжам бойынша, онда біз қатарларды алмастыра аламыз және, осылайша півотымыз орналасқан позициясы болады.
We wish to have ; if this is the case this step is complete, otherwise there is by assumption some with , and we can exchange rows and , thereby obtaining
Our chosen pivot is now at position .
ІІІ кезең: жазбаларды жою
Соңында, t қатарының тиісті еселерін қосу арқылы jt бағанындағы (t,jt) орнындағыдан басқа барлық элементтерді нөлге келтіруге болады. Бұл тиісті матрицаны сол жақтан көбейту арқылы іске асырылады. Дегенмен, матрицаны толық диагональдық ету үшін (t,jt) орнындағы қатардағы нөлдік емес элементтерді де жою қажет. Бұл II қадамдағы амалдарды қатарлардың орнына бағандарға қатысты қайталау арқылы және оң жақтан алынған L матрицасының транспозициясын көбейту арқылы жүзеге асырылуы мүмкін. Жалпы жағдайда, бұл III қадамның бұрынғы қолданылуынан нөл болған элементтердің қайтадан нөлдік емес болуына әкеледі. Алайда, II қадамды қатарлар немесе бағандар үшін қолдану кезінде мәні әрқашан азаятынын ескеру қажет, сондықтан процесс белгілі бір итерациядан кейін тоқтауы керек, нәтижесінде (t,jt) орнындағы элемент оның қатары мен бағанындағы жалғыз нөлдік емес элемент болады. Осы кезде тек (t,jt) орнынан төменгі оң жаққа орналасқан A блогын диагональдау қажет, және алгоритмді тұжырымдамалық тұрғыдан рекурсивті түрде қолдануға болады, бұл блокты жеке матрица ретінде қарастыруға болады. Яғни, t-ны бірге арттырып, I қадамға оралуға болады.
Қолданбалар
Смит нормальды түрі шекті түрде жасалған тізбек модульдері бар тізбек кешенінің гомологиясын есептеу үшін пайдалы. Мысалы, топологияда, ол шекті қарапайым кешеннің немесе CW кешенінің бүтін сандар арқылы есептелген гомологиясын анықтауға қолданылады, себебі мұндай кешендердегі шекаралық операторлар – бүтін сандық матрицалар ғана болып табылады. Сонымен қатар, ол негізгі идеалдық домендегі шекті жасалған модульдердің құрылым теоремасында кездесетін инвариантты факторларды анықтауға мүмкіндік береді, бұл шекті жасалған абелдік топтардың негізгі теоремасын да қамтиды. Смит нормальды түрі бақылау теориясында беріліс және тоқтату нөлдерін есептеу үшін де қолданылады.
Орындау уақытының күрделілігі
N×N матрицасының Смит нормальды түрі A уақытында есептелуі мүмкін. Егер матрица сирегі болса, есептеу әдетте әлдеқайда жылдамдатылады.