Hadamard's maximal determinant problem
હેડમર્ડની મહત્તમ નિર્ધારક સમસ્યા, જેક્સ હેડમર્ડના નામ પરથી નામ આપવામાં આવ્યું છે, તે 1 અથવા-1 સમાન તત્વો સાથે મેટ્રિક્સના સૌથી મોટા નિર્ધારક માટે પૂછે છે. 0 અથવા 1 ની બરાબર તત્વો ધરાવતા મેટ્રિસીસ માટેનો સમાન પ્રશ્ન સમકક્ષ છે કારણ કે, નીચે બતાવ્યા પ્રમાણે, n કદના {1, − 1} મેટ્રિક્સનો મહત્તમ નિર્ધારક એ n − 1 કદના {0,1} મેટ્રિક્સના મહત્તમ નિર્ધારકનો 2n − 1 ગણો છે. આ સમસ્યા હેડમાર્ડે 1893 ના પેપરમાં રજૂ કરી હતી જેમાં તેમણે તેમના પ્રખ્યાત નિર્ધારક બાઉન્ડ રજૂ કર્યા હતા અને સામાન્ય કદના મેટ્રિસીસ માટે વણઉકેલાયેલી રહે છે. હેડામાર્ડની બાઉન્ડ સૂચવે છે કે n કદના {1, −1}-મેટ્રિક્સ મહત્તમ nn/2 પર નિર્ધારક ધરાવે છે. હેડમાર્ડે અવલોકન કર્યું હતું કે સિલ્વેસ્ટરની રચના મેટ્રિસીસના ઉદાહરણો ઉત્પન્ન કરે છે જે જ્યારે n એ 2 ની ઘાત હોય ત્યારે સીમા પ્રાપ્ત કરે છે, અને તેના પોતાના કદ 12 અને 20 ના ઉદાહરણો ઉત્પન્ન કરે છે. તેમણે એ પણ દર્શાવ્યું હતું કે બાઉન્ડ ત્યારે જ પ્રાપ્ત કરી શકાય છે જ્યારે n એ 1,2 અથવા 4 નો ગુણાંક હોય. વધારાના ઉદાહરણો પાછળથી સ્કાર્પિસ અને પાલે દ્વારા અને ત્યારબાદ અન્ય ઘણા લેખકો દ્વારા બનાવવામાં આવ્યા હતા. આવા મેટ્રિસીસ હવે હદામર્ડ મેટ્રિસીસ તરીકે ઓળખાય છે. તેમને સઘન અભ્યાસ મળ્યો છે. મેટ્રિક્સ કદ n જેના માટે n ષ્ણ 1,2, અથવા 3 (મોડ 4) ને ઓછું ધ્યાન મળ્યું છે. પ્રારંભિક પરિણામો બાર્બાને કારણે છે, જેમણે એન ઓડ માટે હેડમર્ડની બાઉન્ડ કડક કરી હતી, અને વિલિયમસન, જેમણે એન = 3,5,6 અને 7 માટે સૌથી મોટા નિર્ધારકો શોધી કાઢ્યા હતા. કેટલાક મહત્વપૂર્ણ પરિણામોમાં બારબા, એહલિચ અને વોજ્તાસને કારણે, n ષ્ણ 1,2, અથવા 3 (મોડ 4) માટે સખત સીમાઓનો સમાવેશ થાય છે, જે જોકે, હંમેશા પ્રાપ્ય ન હોવાનું જાણીતું છે, n ષ્ણ 1 અથવા 2 (મોડ 4) માટે સીમા પ્રાપ્ત કરતા મેટ્રિસીસના કેટલાક અનંત ક્રમ, ચોક્કસ n ષ્ણ 1 અથવા 2 (મોડ 4) માટે સીમા પ્રાપ્ત કરતા સંખ્યાબંધ મેટ્રિસીસ, ચોક્કસ n ષ્ણ 1 અથવા 3 (મોડ 4) માટે સીમા પ્રાપ્ત ન કરતા સંખ્યાબંધ મેટ્રિસીસ, પરંતુ તે સંપૂર્ણ ગણતરી દ્વારા મહત્તમ નિર્ધારક હોવાનું સાબિત થયું છે. આંકડાશાસ્ત્રમાં પ્રયોગોની રચના {1, −1} મેટ્રિક્સ X (જરૂરી નથી કે ચોરસ) નો ઉપયોગ કરે છે, જેના માટે માહિતી મેટ્રિક્સ XTX મહત્તમ નિર્ધારક ધરાવે છે. (XT નોટેશન X ના ટ્રાન્સપોઝને સૂચવે છે.) આવા મેટ્રિસીસને ડી-ઓપ્ટિમલ ડિઝાઇન તરીકે ઓળખવામાં આવે છે. જો X એ ચોરસ મેટ્રિક્સ હોય, તો તે સંતૃપ્ત D-ઓપ્ટિમલ ડિઝાઇન તરીકે ઓળખાય છે. હેડમર્ડ મેટ્રિક્સ n × n હેડમર્ડ મેટ્રિક્સની કોઈપણ બે પંક્તિઓ ઓર્થોગોનલ હોય છે. {1, −1} મેટ્રિક્સ માટે, તેનો અર્થ એ છે કે કોઈપણ બે પંક્તિઓ એન્ટ્રીઓના બરાબર અડધા ભાગમાં અલગ પડે છે, જે ત્યારે અશક્ય છે જ્યારે n એક વિષમ સંખ્યા હોય. જ્યારે n ષ્ણ2 (મોડ 4) હોય, ત્યારે બે પંક્તિઓ કે જે બંને ત્રીજી પંક્તિ માટે ઓર્થોગોનલ હોય તે એકબીજા માટે ઓર્થોગોનલ ન હોઈ શકે. એકસાથે, આ નિવેદનો સૂચવે છે કે n × n હડામર્ડ મેટ્રિક્સ માત્ર ત્યારે જ અસ્તિત્વમાં હોઈ શકે છે જો n = 1,2, અથવા 4 નો ગુણાંક હોય. હેડમર્ડ મેટ્રિક્સનો સારી રીતે અભ્યાસ કરવામાં આવ્યો છે, પરંતુ તે જાણીતું નથી કે દરેક n માટે n × n હેડમર્ડ મેટ્રિક્સ અસ્તિત્વમાં છે કે કેમ જે 4 નો હકારાત્મક ગુણાંક છે. સૌથી નાનો n કે જેના માટે n × n હડામર્ડ મેટ્રિક્સ અસ્તિત્વમાં નથી તે 668 છે. {1, −1} મેટ્રિક્સની સમાનતા અને સામાન્યીકરણ નીચેની કોઈપણ કામગીરી, જ્યારે {1, −1} મેટ્રિક્સ R પર કરવામાં આવે છે, ત્યારે R ના નિર્ધારકને માત્ર બાદબાકી ચિહ્ન દ્વારા બદલાય છેઃ પંક્તિની નકારાત્મકતા. સ્તંભની નકારાત્મકતા. બે હરોળનું આદાનપ્રદાન. બે સ્તંભોનું આદાનપ્રદાન. જો ઉપરોક્ત કામગીરીઓના અમુક ક્રમ દ્વારા R1 ને R2 માં રૂપાંતરિત કરી શકાય તો બે {1, −1} મેટ્રિસીસ, R1 અને R2 ને સમકક્ષ ગણવામાં આવે છે. સમકક્ષ મેટ્રિસીસના નિર્ધારકો સમાન હોય છે, સંભવતઃ સંકેત પરિવર્તન સિવાય, અને પંક્તિઓ અને સ્તંભોના નકારાત્મક અને ક્રમચયો દ્વારા R ને પ્રમાણિત કરવું ઘણીવાર અનુકૂળ હોય છે. A {1, −1} મેટ્રિક્સને સામાન્યીકૃત કરવામાં આવે છે જો તેની પ્રથમ પંક્તિ અને સ્તંભમાંના તમામ ઘટકો 1 ની બરાબર હોય. જ્યારે મેટ્રિક્સનું કદ વિચિત્ર હોય, ત્યારે કેટલીકવાર અલગ સામાન્યીકરણનો ઉપયોગ કરવો ઉપયોગી છે જેમાં દરેક પંક્તિ અને સ્તંભમાં 1 તત્વોની સમ સંખ્યા અને 1 તત્વોની વિષમ સંખ્યા હોય છે. આમાંથી કોઈપણ સામાન્યીકરણ પ્રથમ બે કામગીરીનો ઉપયોગ કરીને પૂર્ણ કરી શકાય છે. {1, −1} અને {0,1} મેટ્રિક્સ માટે મહત્તમ નિર્ધારક સમસ્યાઓનું જોડાણ સામાન્યીકૃત n × n {1, −1} મેટ્રિક્સના સમૂહમાંથી (n − 1) × (n-1) {0,1} મેટ્રિક્સના સમૂહમાં એક-થી-એક નકશો છે, જેમાં નિર્ધારકની તીવ્રતા 21 − n ના પરિબળ દ્વારા ઘટાડવામાં આવે છે. આ નકશામાં નીચેના પગલાંઓ છે. {1, −1} મેટ્રિક્સની પંક્તિ 1 ને પંક્તિ 2 થી n સુધી બાદ કરો. (આ નિર્ધારકને બદલતું નથી.) (n−1) × (n−1) પેટા મેટ્રિક્સને બહાર કાઢો જેમાં પંક્તિઓ 2 થી n અને સ્તંભો 2 થી n છે. આ મેટ્રિક્સમાં તત્વો 0 અને −2 છે. (આ પેટા મેટ્રિક્સનો નિર્ધારક મૂળ મેટ્રિક્સ જેવો જ છે, જે પગલું 1 માં મેળવેલા મેટ્રિક્સના સ્તંભ 1 પર કોફેક્ટર વિસ્તરણ કરીને જોઈ શકાય છે.) {0,1} મેટ્રિક્સ મેળવવા માટે સબમેટ્રિક્સને −2 વડે વિભાજીત કરો. (આ નિર્ધારકને (−2) 1 − n વડે ગુણાકાર કરે છે.) ઉદાહરણોઃ આ ઉદાહરણમાં, મૂળ મેટ્રિક્સમાં નિર્ધારક −16 છે અને તેની છબીમાં નિર્ધારક 2 = −16· (−2) −3 છે. {0,1} મેટ્રિક્સનો નિર્ધારક એક પૂર્ણાંક હોવાથી, n × n {1, − 1} મેટ્રિક્સનો નિર્ધારક 2n − 1 નો પૂર્ણાંક ગુણાંક છે. મહત્તમ નિર્ધારક ગ્રામ મેટ્રિક્સ પર ઉપલી સીમાઓ ધારો કે R એ n બાય n {1, −1} મેટ્રિક્સ છે. આર ના ગ્રામ મેટ્રિક્સને મેટ્રિક્સ જી = આરઆરટી તરીકે વ્યાખ્યાયિત કરવામાં આવે છે. આ વ્યાખ્યા પરથી તે અનુસરે છે કે G એક પૂર્ણાંક મેટ્રિક્સ છે, તે સપ્રમાણ છે, હકારાત્મક-સમાન છે, સતત કર્ણ ધરાવે છે જેનું મૂલ્ય n બરાબર છે. R ની પંક્તિઓને નકારવાથી અથવા તેમને ક્રમચય લાગુ કરવાથી G ની પંક્તિઓ અને અનુરૂપ સ્તંભો બંને પર સમાન નકારાત્મકતા અને ક્રમચય લાગુ થાય છે. આપણે મેટ્રિક્સ G′ = RTR પણ વ્યાખ્યાયિત કરી શકીએ છીએ. મેટ્રિક્સ G એ વેક્ટરના સમૂહનો સામાન્ય ગ્રામ મેટ્રિક્સ છે, જે R ની પંક્તિઓના સમૂહમાંથી મેળવવામાં આવે છે, જ્યારે G′ એ R ના સ્તંભોના સમૂહમાંથી મેળવેલ ગ્રામ મેટ્રિક્સ છે. A મેટ્રિક્સ R જેના માટે G = G′ એક સામાન્ય મેટ્રિક્સ છે. દરેક જાણીતા મહત્તમ-નિર્ધારક મેટ્રિક્સ સામાન્ય મેટ્રિક્સની સમકક્ષ હોય છે, પરંતુ તે જાણીતું નથી કે આ હંમેશા કેસ છે કે નહીં. હેડમર્ડની બાઉન્ડ (તમામ n માટે) હેડમર્ડની બાઉન્ડ એ નોંધ કરીને મેળવી શકાય છે કે |det R | = (ડેટ G) 1/2 ≤ (ડેટ nI) 1/2 = nn/2, જે નિરીક્ષણનું પરિણામ છે કે nI, જ્યાં I એ n બાય n આઇડેન્ટિટી મેટ્રિક્સ છે, તે 1-4 ના ગુણધર્મોને સંતોષતા મેટ્રિક્સમાં મહત્તમ નિર્ધારકનો અનન્ય મેટ્રિક્સ છે. તે ડીટ આર એ 2n−1 નો પૂર્ણાંક ગુણાંક હોવો જોઈએ જેનો ઉપયોગ અન્ય પ્રદર્શન પ્રદાન કરવા માટે થઈ શકે છે કે હેડામાર્ડની બાઉન્ડ હંમેશા પ્રાપ્ય નથી. જ્યારે n વિષમ હોય, ત્યારે બંધાયેલ nn/2 ક્યાં તો બિન-પૂર્ણાંક અથવા વિષમ હોય છે, અને તેથી જ્યારે n = 1 હોય ત્યારે તે અપ્રાપ્ય હોય છે. જ્યારે n = 2k અને k વિષમ હોય, ત્યારે હેડામાર્ડની બાઉન્ડને વિભાજીત કરતી 2 ની સૌથી વધુ ઘાત 2k હોય છે, જે n = 2 સિવાય 2n−1 કરતા ઓછી હોય છે. તેથી, જ્યાં સુધી n = 1,2, અથવા 4 નો ગુણાંક ન હોય ત્યાં સુધી હેડમર્ડની બાઉન્ડ અપ્રાપ્ય છે. જ્યારે n વિષમ હોય, ત્યારે ગ્રામ મેટ્રિક્સ માટે ગુણધર્મ 1 ને G થી મજબૂત કરી શકાય છે, તે એક વિષમ-પૂર્ણાંક મેટ્રિક્સ છે. આ એક વધુ તીક્ષ્ણ ઉપલી બાઉન્ડ મેળવવાની મંજૂરી આપે છેઃ |det R | = (ડેટ G) 1/2 ≤ (ડેટ (n-1) I + J) 1/2 = (2n−1) 1/2 (n−1) (n−1)/2, જ્યાં J એ ઓલ-વન મેટ્રિક્સ છે. અહીં (n-1) I + J એ મહત્તમ-નિર્ધારક મેટ્રિક્સ છે જે સુધારેલા ગુણધર્મ 1 અને ગુણધર્મો 2-4 ને સંતોષે છે. તે પંક્તિઓના કોઈપણ સમૂહ અને સ્તંભોના અનુરૂપ સમૂહને −1 વડે ગુણાકાર કરવા માટે અનન્ય છે. જ્યાં સુધી 2n−1 એક સંપૂર્ણ વર્ગ ન હોય ત્યાં સુધી સીમા પ્રાપ્ત કરી શકાતી નથી, અને તેથી જ્યારે n ષ્ણ 3 (મોડ 4) હોય ત્યારે તે ક્યારેય પ્રાપ્ત કરી શકાતી નથી. ઇલિચ-વોજ્તાસ n ષ્ણ 2 (મોડ 4) માટે બંધાયેલ છે જ્યારે n સમ હોય, ત્યારે R ની પંક્તિઓના સમૂહને બે ઉપગણમાં વિભાજિત કરી શકાય છે. સમ પ્રકારની હરોળમાં ઘટકોની સંખ્યા 1 અને ઘટકોની સંખ્યા-1 હોય છે. વિષમ પ્રકારની હરોળમાં તત્વોની વિષમ સંખ્યા 1 અને તત્વોની વિષમ સંખ્યા-1 હોય છે. એક જ પ્રકારની બે હરોળનું ડોટ પ્રોડક્ટ n (મોડ 4) માટે એકરૂપ છે; વિરુદ્ધ પ્રકારની બે હરોળનું ડોટ પ્રોડક્ટ n + 2 (મોડ 4) માટે એકરૂપ છે. જ્યારે n ષ્ણ2 (મોડ 4) હોય, ત્યારે આ સૂચવે છે કે, R ની પંક્તિઓને ક્રમબદ્ધ કરીને, આપણે પ્રમાણભૂત સ્વરૂપ ધારણ કરી શકીએ છીએ, જ્યાં A અને D સપ્રમાણ પૂર્ણાંક મેટ્રિસીસ છે, જેમના ઘટકો 2 (મોડ 4) સાથે એકરૂપ છે અને B એ એક મેટ્રિક્સ છે, જેના ઘટકો 0 (મોડ 4) સાથે એકરૂપ છે. 1964માં, એહલિચ અને વોજ્તાસે સ્વતંત્ર રીતે દર્શાવ્યું હતું કે આ સ્વરૂપના મહત્તમ નિર્ધારક મેટ્રિક્સમાં, A અને D બંનેનું કદ n/2 અને (n−2) I + 2J બરાબર છે જ્યારે B એ શૂન્ય મેટ્રિક્સ છે. આ શ્રેષ્ઠ સ્વરૂપ પંક્તિઓના કોઈપણ સમૂહ અને સ્તંભોના અનુરૂપ સમૂહને −1 વડે ગુણાકાર કરવા અને પંક્તિઓ અને સ્તંભોમાં એક સાથે ક્રમચય લાગુ કરવા માટે અનન્ય છે. આ બંધાયેલ ડેટ R ≤ (2n−2) (n−2) (n−2)/2 સૂચવે છે. એહલિચે દર્શાવ્યું હતું કે જો R બાઉન્ડ પ્રાપ્ત કરે છે, અને જો R ની પંક્તિઓ અને સ્તંભોને ક્રમબદ્ધ કરવામાં આવે છે જેથી G = RRT અને G′ = RTR બંને પ્રમાણભૂત સ્વરૂપ ધરાવે છે અને યોગ્ય રીતે સામાન્ય બને છે, તો આપણે લખી શકીએ છીએ કે W, X, Y, અને Z એ (n/2) × (n/2) મેટ્રિક્સ છે જેમાં સતત પંક્તિ અને સ્તંભનો સરવાળો w, x, y, અને z છે જે z = −w, y = x, અને w2 + x2 = 2n − 2 ને સંતોષે છે. તેથી જ્યાં સુધી 2n−2 બે ચોરસના સરવાળા તરીકે વ્યક્ત ન થાય ત્યાં સુધી એલિચ-વોજ્તાસની સીમા પ્રાપ્ત કરી શકાતી નથી. જ્યારે n વિષમ હોય, ત્યારે પંક્તિઓને −1 વડે ગુણાકાર કરવાની સ્વતંત્રતાનો ઉપયોગ કરીને, કોઈ એવી શરત લાદી શકે છે કે R ની દરેક હરોળમાં ઘટકોની સંખ્યા 1 અને ઘટકોની સંખ્યા −1 હોય. તે દર્શાવી શકાય છે કે, જો આ સામાન્યીકરણ ધારવામાં આવે, તો G નો ગુણધર્મ 1 ને G થી મજબૂત કરી શકાય છે, જે n (મોડ 4) સાથે એકરૂપ પૂર્ણાંક તત્વો સાથેનું મેટ્રિક્સ છે. જ્યારે n ષ્ણ 1 (મોડ 4) હોય, ત્યારે બાર્બાનું શ્રેષ્ઠ સ્વરૂપ આ મજબૂત ગુણધર્મને સંતોષે છે, પરંતુ જ્યારે n ષ્ણ 3 (મોડ 4) હોય, ત્યારે તે સંતોષતું નથી. આનો અર્થ એ છે કે પછીના કિસ્સામાં બાઉન્ડને તીક્ષ્ણ કરી શકાય છે. એહલિચે દર્શાવ્યું હતું કે જ્યારે n ષ્ણ 3 (મોડ 4) હોય, ત્યારે મજબૂત ગુણધર્મ 1 સૂચવે છે કે Gનું મહત્તમ-નિર્ધારક સ્વરૂપ B − J તરીકે લખી શકાય છે, જ્યાં J એ ઓલ-વન મેટ્રિક્સ છે અને B એ બ્લોક-ડાયાગોનલ મેટ્રિક્સ છે, જેના વિકર્ણ બ્લોક (n-3) I + 4J સ્વરૂપના હોય છે. વધુમાં, તેમણે દર્શાવ્યું કે શ્રેષ્ઠ સ્વરૂપમાં, બ્લોકની સંખ્યા, s, નીચે કોષ્ટકમાં બતાવ્યા પ્રમાણે n પર આધાર રાખે છે, અને દરેક બ્લોકનું કદ r અથવા કદ r + 1 હોય છે જ્યાં n = 11 સિવાય જ્યાં બે શક્યતાઓ હોય, શ્રેષ્ઠ સ્વરૂપ પંક્તિઓના કોઈપણ સમૂહ અને સ્તંભોના અનુરૂપ સમૂહને −1 વડે ગુણાકાર કરવા અને પંક્તિઓ અને સ્તંભોમાં એક સાથે ક્રમચય લાગુ કરવા માટે અનન્ય છે. આ શ્રેષ્ઠ સ્વરૂપ એ સીમા તરફ દોરી જાય છે જ્યાં v = n − rs એ r + 1 કદના બ્લોકની સંખ્યા છે અને u = s − v એ r કદના બ્લોકની સંખ્યા છે. કોહેને બાઉન્ડનું વિશ્લેષણ કર્યું અને નક્કી કર્યું કે, n = 3 સિવાય, તે માત્ર n = 112t2 ± 28t + 7 માટે કેટલાક હકારાત્મક પૂર્ણાંક t માટે પૂર્ણાંક છે. તમુરાએ હાસ-મિન્કોવ્સ્કી પ્રમેયનો ઉપયોગ કરીને બાઉન્ડની પ્રાપ્તિ પર વધારાના નિયંત્રણો મેળવ્યા હતા. માપ 21 સુધીના મહત્તમ નિર્ધારકો n = 21 કદ સુધીના {1, −1} મેટ્રિસીસના મહત્તમ નિર્ધારકો નીચેના કોષ્ટકમાં આપવામાં આવ્યા છે. સાઇઝ 22 એ સૌથી નાનો ઓપન કેસ છે. કોષ્ટકમાં, D (n) એ 2n−1 વડે ભાગેલા મહત્તમ નિર્ધારકને રજૂ કરે છે. સમાનરૂપે, D (n) એ n − 1 કદના {0,1} મેટ્રિક્સના મહત્તમ નિર્ધારકને રજૂ કરે છે. સંદર્ભો સંયુક્ત રચના મેટ્રિક્સ ગણિતમાં વણઉકેલાયેલી સમસ્યાઓ