Hadamard's maximal determinant problem
ہڈمارڈ کا زیادہ سے زیادہ تعین کرنے والا مسئلہ، جس کا نام جیکس ہڈمارڈ کے نام پر رکھا گیا ہے، میٹرکس کا سب سے بڑا تعین کرنے والا 1 یا-1 کے برابر عناصر کے ساتھ پوچھتا ہے۔ 0 یا 1 کے برابر عناصر والے میٹرکس کے لیے ہم آہنگ سوال مساوی ہے کیونکہ، جیسا کہ ذیل میں دکھایا جائے گا، سائز n کے a {1, − 1} میٹرکس کا زیادہ سے زیادہ تعین کرنے والا 2n − 1 گنا زیادہ سے زیادہ تعین کرنے والا n − 1 میٹرکس کا زیادہ سے زیادہ تعین کرنے والا ہے۔ یہ مسئلہ ہڈمارڈ نے 1893 کے مقالے میں پیش کیا تھا جس میں انہوں نے اپنا مشہور ڈیٹرمیننٹ باؤنڈ پیش کیا تھا اور عام سائز کے میٹرکس کے لیے حل شدہ نہیں ہے۔ ہڈمارڈ کے باؤنڈ سے یہ ظاہر ہوتا ہے کہ n سائز کے {1, −1}-میٹرکس زیادہ سے زیادہ nn/2 پر فیصلہ کن ہوتے ہیں۔ ہڈمارڈ نے مشاہدہ کیا کہ سلویسٹر کی تعمیر میٹرکس کی مثالیں پیش کرتی ہے جو اس وقت حد تک پہنچتی ہیں جب n 2 کی طاقت ہوتی ہے، اور اس نے اپنے سائز 12 اور 20 کی مثالیں پیش کیں۔ انہوں نے یہ بھی دکھایا کہ باؤنڈ صرف اس وقت حاصل کیا جا سکتا ہے جب n 1، 2، یا 4 کے ضرب کے برابر ہو۔ اضافی مثالیں بعد میں سکارپس اور پیلے اور اس کے بعد بہت سے دوسرے مصنفین نے تیار کیں۔ اس طرح کے میٹرکس کو اب ہڈمارڈ میٹرکس کے نام سے جانا جاتا ہے۔ انہوں نے گہری تحقیق حاصل کی ہے۔ میٹرکس سائز n جس کے لیے n ष्ण 1، 2، یا 3 (موڈ 4) کو کم توجہ ملی ہے۔ ابتدائی نتائج باربا کی وجہ سے ہیں، جنہوں نے ہڈمارڈ کی حد کو n طاق کے لیے سخت کیا، اور ولیمسن، جنہوں نے n = 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 کے تعین کنندہ کو صرف مائنس کے نشان سے تبدیل کرتا ہے: ایک صف کی نفی۔ کالم کی نفی۔ دو قطاروں کا تبادلہ۔ دو کالموں کا تبادلہ۔ دو {1, −1} میٹرکس، R1 اور R2، کو مساوی سمجھا جاتا ہے اگر 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 تک گھٹا دیں۔ (اس سے تعین کنندہ تبدیل نہیں ہوتا ہے۔) صفوں 2 سے n اور کالم 2 سے n پر مشتمل (n−1) × (n−1) ذیلی میٹرکس نکالیں۔ اس میٹرکس میں عناصر 0 اور −2 ہیں۔ (اس ذیلی میٹرکس کا تعین کرنے والا اصل میٹرکس جیسا ہی ہے، جیسا کہ مرحلہ 1 میں حاصل کردہ میٹرکس کے کالم 1 پر کوفیکٹر کی توسیع انجام دینے سے دیکھا جا سکتا ہے۔) {0,1} میٹرکس حاصل کرنے کے لیے ذیلی میٹرکس کو −2 سے تقسیم کریں۔ (یہ تعین کنندہ کو (−2) 1 − n سے ضرب دیتا ہے۔) مثال: اس مثال میں، اصل میٹرکس کا ڈیٹرمیننٹ −16 ہے اور اس کی تصویر کا ڈیٹرمیننٹ 2 = −16· (−2) −3 ہے۔ چونکہ a {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 ہے جو 2n−1 سے کم ہے جب تک کہ n = 2 نہ ہو۔ لہذا، ہڈمارڈ کا باؤنڈ ناقابل حصول ہے جب تک کہ 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 ہو۔ یہ دکھایا جا سکتا ہے کہ، اگر یہ نارملائزیشن فرض کی جاتی ہے، تو 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 کے لیے ایک انٹیجر ہے۔ تمورا نے ہاسی-منکوسکی تھیوریم کا استعمال کرتے ہوئے باؤنڈ کے حصول پر اضافی پابندیاں اخذ کیں جو کہ کواڈریٹک شکلوں کی عقلی مساوات پر ہے، اور یہ ظاہر کیا کہ سب سے چھوٹا n> 3 جس کے لیے ایلچ کا باؤنڈ قابل فہم ہے 511 ہے۔ سائز 21 تک کے زیادہ سے زیادہ تعین کنندگان سائز n = 21 تک کے {1, −1} میٹرکس کے زیادہ سے زیادہ تعین کنندگان درج ذیل جدول میں دیے گئے ہیں۔ سائز 22 سب سے چھوٹا کھلا کیس ہے۔ جدول میں، D (n) 2n−1 سے تقسیم شدہ زیادہ سے زیادہ تعین کنندہ کی نمائندگی کرتا ہے۔ مساوی طور پر، D (n) سائز n−1 کے {0,1} میٹرکس کے زیادہ سے زیادہ تعین کنندہ کی نمائندگی کرتا ہے۔ حوالہ جات مشترکہ ڈیزائن میٹرکس ریاضی میں حل نہ ہونے والے مسائل