Category: Matrix Algebra

#pragma once
#include <vector>

class Inverse
{
public:
	static bool Compute(
		int n,
		std::vector<std::vector<double>>& M,
		std::vector<std::vector<double>>& X);
	static void CharacteristicPolynomial(
		int n, std::vector<double>& a,
		std::vector<std::vector<double>>& C,
		std::vector<std::vector<double>>& M,
		std::vector<std::vector<double>>& Madj);
};

// Reference: 5.2: The Characteristic Polynomial - Mathematics LibreTexts
#include "Inverse.h"
#include <vector>

bool Inverse::Compute(
	int n,
	std::vector<std::vector<double>>& M,
	std::vector<std::vector<double>>& X) {
	double d = 0.0;
	int i = 0, j = 0, k = 0, l = 0;
	std::vector<double> C(n);
	std::vector<std::vector<double>> B;
	B.resize(n);
	X.resize(n);
	for (i = 0; i < n; i++)
	{
		B[i].resize(n);
		X[i].resize(n);
		for (j = 0; j < n; j++)
		{
			B[i][j] = 0.0;
			X[i][j] = 0.0;
		}
		B[i][i] = 1.0;
	}
	j = -1;
Step2:
	j++;
	if (j == n)
		goto Step6;
	for (i = j; i < n; i++) {
		if (M[i][j] != 0)
			break;
	}
	if (i == n)
		return false;
	if (i > j) {
		for (l = j; l < n; l++) {
			double temp = M[i][l];
			M[i][l] = M[j][l];
			M[j][l] = temp;
		}
		for (l = 0; l < n; l++) {
			double temp = B[i][l];
			B[i][l] = B[j][l];
			B[j][l] = temp;
		}
	}
	d = 1.0 / M[j][j];
	for (k = j + 1; k < n; k++) {
		C[k] = d * M[k][j];
	}
	for (k = j + 1; k < n; k++) {
		for (l = j + 1; l < n; l++) {
			M[k][l] -= C[k] * M[j][l];
		}
	}
	for (k = j + 1; k < n; k++) {
		for (l = 0; l < n; l++) {
			B[k][l] -= C[k] * B[j][l];
		}
	}
	goto Step2;
Step6:
	for (i = n - 1; i >= 0; i--) {
		std::vector<double> sum(n, 0);
		for (j = i + 1; j < n; j++) {
			for (k = 0; k < n; k++) {
				sum[k] += M[i][j] * X[j][k];
			}
		}
		for (j = 0; j < n; j++)
			X[i][j] = (B[i][j] - sum[j]) / M[i][i];
	}
	return true;
}

double delta(int i, int j) {
	return i == j ? 1.0 : 0.0;
}

void Inverse::CharacteristicPolynomial(
	int n, std::vector<double>& a,
	std::vector<std::vector<double>>& C,
	std::vector<std::vector<double>>& M,
	std::vector<std::vector<double>>& Madj) {
	int i = 0, j = 0, k = 0, l = 0;
	std::vector<double> X(n);
	std::vector<std::vector<double>> MC;
	a.resize(n + 1LL);
	C.resize(n);
	M.resize(n);
	MC.resize(n);
	Madj.resize(n);
	for (i = 0; i < n; i++) {
		C[i].resize(n);
		M[i].resize(n);
		MC[i].resize(n);
		Madj[i].resize(n);
		for (j = 0; j < n; j++) {
			C[i][j] = delta(i, j);
		}
	}
	a[0] = 1.0;
	i = 0;
Step2:
	i++;
	if (i == n) {
		for (j = 0; j < n; j++) {
			for (k = 0; k < n; k++) {
				double sum = 0.0;
				for (l = 0; l < n; l++) {
					sum += M[j][l] * C[l][k];
				}
				MC[j][k] = sum;
			}
		}
		double trace = 0.0;
		for (j = 0; j < n; j++) {
			trace += MC[j][j];
		}
		a[n] = -trace / n;
		for (j = 0; j < n; j++) {
			for (k = 0; k < n; k++) {
				Madj[j][k] = pow(-1, n - 1) * C[j][k];
			}
		}
		return;
	}
	for (j = 0; j < n; j++) {
		for (k = 0; k < n; k++) {
			double sum = 0.0;
			for (l = 0; l < n; l++) {
				sum += M[j][l] * C[l][k];
			}
			MC[j][k] = sum;
		}
	}
	for (j = 0; j < n; j++) {
		for (k = 0; k < n; k++) {
			C[j][k] = MC[j][k];
		}
	}
	double tr = 0.0;
	for (j = 0; j < n; j++) {
		tr += C[j][j];
	}
	a[i] = -tr / i;
	for (j = 0; j < n; j++) {
		for (k = 0; k < n; k++) {
			C[j][k] += a[i] * delta(j, k);
		}
	}
	goto Step2;
}

// Reference: "A Course in Computational
// Algebraic Number Theory by Henri Cohen
// Chapter 2 Algorithm 2.2.1 and Algorithm
// 2.2.3

#pragma once
#include <vector>

class Determinants
{
public:
	static bool GaussianElimnation(
		int n,
		std::vector<std::vector<double>>& M,
		std::vector<double> B,
		std::vector<double> X);
	static bool Determinant(
		double& det, int n,
		std::vector<std::vector<double>>& M);
};

#include "Determinants.h"

bool Determinants::GaussianElimnation(
	int n,
	std::vector<std::vector<double>>& M,
	std::vector<double> B,
	std::vector<double> X) {
	double d = 0.0;
	int i = 0, j = -1, k = 0, l = 0;
	std::vector<double> C(n);
Step2:
	j++;
	if (j == n)
		goto Step6;

	for (i = j; i < n; i++) {
		if (M[i][j] > 0)
			break;
	}
	if (i == n)
		return false;
	if (i > j) {
		for (l = j; j < n; l++) {
			double temp = M[i][l];
			M[i][l] = M[j][l];
			M[j][l] = temp;
			temp = B[i];
			B[i] = B[j];
			B[j] = temp;
		}
	}
	d = 1.0 / M[j][j];
	for (k = j + 1; k < n; k++) {
		C[k] = d * M[k][j];
	}
	for (k = j + 1; k < n; k++) {
		for (l = j + 1; l < n; l++) {
			M[k][l] -= C[k] * M[j][l];
		}
	}
	for (k = j + 1; k < n; k++) {
		B[k] -= C[k] * B[j];
	}
	goto Step2;
Step6:
	for (i = n - 1; i >= 0; i--) {
		double sum = 0.0;
		for (j = i + 1; j < n; j++) {
			sum += M[i][j] * X[j];
		}
		X[i] = (B[i] - sum) / M[i][i];
	}
	return true;
}

bool Determinants::Determinant(
	double& det, int n,
	std::vector<std::vector<double>>& M) {
	double d = 0.0, x = 1.0;
	int i = 0, j = -1, k = 0, l = 0;
	std::vector<double> C(n, 0);
Step2:
	j++;
	if (j == n) {
		det = x;
		return true;
	}
	for (i = j; i < n; i++) {
		if (M[i][j] != 0.0)
			break;
	}
	if (i == n) {
		det = 0.0;
		return false;
	}
	if (i > j) {
		for (l = j; j < n; l++) {
			double temp = M[i][l];
			M[i][l] = M[j][l];
			M[j][l] = temp;
		}
		x = -x;
	}
	d = 1.0 / M[j][j];
	for (k = j + 1; k < n; k++) {
		C[k] = d * M[k][j];
	}
	for (k = j + 1; k < n; k++) {
		for (l = j + 1; l < n; l++) {
			M[k][l] -= C[k] * M[j][l];
		}
	}
	x *= M[j][j];
	goto Step2;
}

// ComputeRealDeterminant.cpp : Defines the entry point for the application.
//

#include "framework.h"
#include "ComputeRealDeterminant.h"
#include "Determinants.h"
#include <string>
#include <vector>

#define MAX_LOADSTRING 100

// Global Variables:
HINSTANCE hInst;                                // current instance
WCHAR szTitle[MAX_LOADSTRING];                  // The title bar text
WCHAR szWindowClass[MAX_LOADSTRING];            // the main window class name
WCHAR line[128], numWstr[128];
WCHAR inpStr[16384], outStr[16384];

// Forward declarations of functions included in this code module:
ATOM                MyRegisterClass(HINSTANCE hInstance);
BOOL                InitInstance(HINSTANCE, int);
LRESULT CALLBACK    WndProc(HWND, UINT, WPARAM, LPARAM);
INT_PTR CALLBACK    About(HWND, UINT, WPARAM, LPARAM);
INT_PTR CALLBACK    DataInputDialog(HWND, UINT, WPARAM, LPARAM);

int APIENTRY wWinMain(_In_ HINSTANCE hInstance,
                     _In_opt_ HINSTANCE hPrevInstance,
                     _In_ LPWSTR    lpCmdLine,
                     _In_ int       nCmdShow)
{
    UNREFERENCED_PARAMETER(hPrevInstance);
    UNREFERENCED_PARAMETER(lpCmdLine);

    // TODO: Place code here.

    // Initialize global strings
    LoadStringW(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);
    LoadStringW(hInstance, IDC_COMPUTEREALDETERMINANT, szWindowClass, MAX_LOADSTRING);
    MyRegisterClass(hInstance);

    // Perform application initialization:
    if (!InitInstance (hInstance, nCmdShow))
    {
        return FALSE;
    }

    HACCEL hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_COMPUTEREALDETERMINANT));

    MSG msg;

    // Main message loop:
    while (GetMessage(&msg, nullptr, 0, 0))
    {
        if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
        {
            TranslateMessage(&msg);
            DispatchMessage(&msg);
        }
    }

    return (int) msg.wParam;
}

//
//  FUNCTION: MyRegisterClass()
//
//  PURPOSE: Registers the window class.
//
ATOM MyRegisterClass(HINSTANCE hInstance)
{
    WNDCLASSEXW wcex = { 0 };

    wcex.cbSize = sizeof(WNDCLASSEX);

    wcex.style          = CS_HREDRAW | CS_VREDRAW;
    wcex.lpfnWndProc    = WndProc;
    wcex.cbClsExtra     = 0;
    wcex.cbWndExtra     = 0;
    wcex.hInstance      = hInstance;
    wcex.hIcon          = LoadIcon(hInstance, MAKEINTRESOURCE(IDI_COMPUTEREALDETERMINANT));
    wcex.hCursor        = LoadCursor(nullptr, IDC_ARROW);
    wcex.hbrBackground  = (HBRUSH)(COLOR_WINDOW+1);
    wcex.lpszMenuName   = MAKEINTRESOURCEW(IDC_COMPUTEREALDETERMINANT);
    wcex.lpszClassName  = szWindowClass;
    wcex.hIconSm        = LoadIcon(wcex.hInstance, MAKEINTRESOURCE(IDI_SMALL));

    return RegisterClassExW(&wcex);
}

//
//   FUNCTION: InitInstance(HINSTANCE, int)
//
//   PURPOSE: Saves instance handle and creates main window
//
//   COMMENTS:
//
//        In this function, we save the instance handle in a global variable and
//        create and display the main program window.
//
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{
   hInst = hInstance; // Store instance handle in our global variable

   HWND hWnd = CreateWindowW(szWindowClass, szTitle, WS_OVERLAPPEDWINDOW,
      CW_USEDEFAULT, 0, CW_USEDEFAULT, 0, nullptr, nullptr, hInstance, nullptr);

   if (!hWnd)
   {
      return FALSE;
   }

   ShowWindow(hWnd, nCmdShow);
   UpdateWindow(hWnd);

   return TRUE;
}

//
//  FUNCTION: WndProc(HWND, UINT, WPARAM, LPARAM)
//
//  PURPOSE: Processes messages for the main window.
//
//  WM_COMMAND  - process the application menu
//  WM_PAINT    - Paint the main window
//  WM_DESTROY  - post a quit message and return
//
//
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{
    switch (message)
    {
    case WM_COMMAND:
        {
            int wmId = LOWORD(wParam);
            // Parse the menu selections:
            switch (wmId)
            {
            case IDM_ABOUT:
                DialogBox(hInst, MAKEINTRESOURCE(IDD_ABOUTBOX), hWnd, About);
                break;
            case IDM_START:
                DialogBox(hInst, MAKEINTRESOURCE(IDD_DATA_INPUT_DIALOG), hWnd,
                    DataInputDialog);
                break;
            case IDM_EXIT:
                DestroyWindow(hWnd);
                break;
            default:
                return DefWindowProc(hWnd, message, wParam, lParam);
            }
        }
        break;
    case WM_PAINT:
        {
            PAINTSTRUCT ps;
            HDC hdc = BeginPaint(hWnd, &ps);
            // TODO: Add any drawing code that uses hdc here...
            EndPaint(hWnd, &ps);
        }
        break;
    case WM_DESTROY:
        PostQuitMessage(0);
        break;
    default:
        return DefWindowProc(hWnd, message, wParam, lParam);
    }
    return 0;
}

// Message handler for about box.
INT_PTR CALLBACK About(HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam)
{
    UNREFERENCED_PARAMETER(lParam);
    switch (message)
    {
    case WM_INITDIALOG:
        return (INT_PTR)TRUE;

    case WM_COMMAND:
        if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL)
        {
            EndDialog(hDlg, LOWORD(wParam));
            return (INT_PTR)TRUE;
        }
        break;
    }
    return (INT_PTR)FALSE;
}

INT_PTR CALLBACK DataInputDialog(
    HWND hDlg, UINT message, WPARAM wParam, LPARAM lParam) {
    static int n = 0;
    static std::wstring wstr;
    static std::vector < std::vector<double>> A;
    static HFONT hFont = nullptr;
    static HWND hEditMultiline1 = nullptr;
    static HWND hEditMultiline2 = nullptr;
    UNREFERENCED_PARAMETER(lParam);
    switch (message) {
    case WM_INITDIALOG:
        SendDlgItemMessage(hDlg, IDC_COMBO_N, CB_ADDSTRING, 0, (LPARAM)L"2");
        SendDlgItemMessage(hDlg, IDC_COMBO_N, CB_ADDSTRING, 0, (LPARAM)L"3");
        SendDlgItemMessage(hDlg, IDC_COMBO_N, CB_ADDSTRING, 0, (LPARAM)L"4");
        SendDlgItemMessage(hDlg, IDC_COMBO_N, CB_ADDSTRING, 0, (LPARAM)L"5");
        SendDlgItemMessage(hDlg, IDC_COMBO_N, CB_ADDSTRING, 0, (LPARAM)L"6");
        SendDlgItemMessage(hDlg, IDC_COMBO_N, CB_ADDSTRING, 0, (LPARAM)L"7");
        SendDlgItemMessage(hDlg, IDC_COMBO_N, CB_ADDSTRING, 0, (LPARAM)L"8");
        SendDlgItemMessage(hDlg, IDC_COMBO_N, CB_SETCURSEL, 0, 0);
        hFont = CreateFont(
            -MulDiv(10, GetDeviceCaps(GetDC(hDlg), LOGPIXELSY), 72),
            0, 0, 0, FW_BOLD, FALSE, FALSE, FALSE,
            DEFAULT_CHARSET, OUT_DEFAULT_PRECIS,
            CLIP_DEFAULT_PRECIS, DEFAULT_QUALITY,
            FIXED_PITCH | FF_MODERN,
            TEXT("Courier New")
        );
        hEditMultiline1 = CreateWindowEx(
            WS_EX_CLIENTEDGE,                       // Extended style for sunken border
            TEXT("EDIT"),                           // Class name
            TEXT(""),                               // Initial text (can be blank)
            WS_CHILD | WS_VISIBLE | WS_VSCROLL |
            ES_LEFT | ES_MULTILINE | ES_AUTOVSCROLL,
            10, 100, 250, 250,                      // Position and size
            hDlg,                                   // Parent window handle
            (HMENU)IDC_EDIT_MULTILINE1,              // Unique control ID
            hInst,                                  // Application instance
            NULL                                    // Extra parameter
        );
        hEditMultiline2 = CreateWindowEx(
            WS_EX_CLIENTEDGE,                       // Extended style for sunken border
            TEXT("EDIT"),                           // Class name
            TEXT(""),                               // Initial text (can be blank)
            WS_CHILD | WS_VISIBLE  | ES_LEFT | ES_READONLY,
            120, 360, 120, 30,                      // Position and size
            hDlg,                                   // Parent window handle
            (HMENU)IDC_EDIT_MULTILINE2,             // Unique control ID
            hInst,                                  // Application instance
            NULL                                    // Extra parameter
        );
        break;
    case WM_COMMAND:
        if (LOWORD(wParam) == IDC_BUTTON_COMPUTE) {
            GetDlgItemText(hDlg, IDC_COMBO_N, inpStr, 16384);
            WCHAR* endptr = nullptr;
            n = (int)wcstol(inpStr, &endptr, 10);
            A.resize(n);
            GetDlgItemText(hDlg, IDC_EDIT_MULTILINE1, inpStr, 16384);
            int k = 0;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    A[i].resize(n);
                    int l = 0; 
                    while (inpStr[k] != L' ') {
                        numWstr[l++] = inpStr[k++];
                    }
                    k++;
                    numWstr[l++] = L'\0';
                    A[i][j] = (double)wcstof(numWstr, &endptr);
                }
            }
            double det = 0.0;
            bool result = Determinants::Determinant(det, n, A);
            swprintf_s(line, 128, L"%lf", det);
            SetDlgItemText(hDlg, IDC_EDIT_MULTILINE2, line);
            break;
        }
        if (LOWORD(wParam) == IDOK || LOWORD(wParam) == IDCANCEL) {
            EndDialog(hDlg, LOWORD(wParam));
            return (INT_PTR)TRUE;
        }
        break;
    }
    return (INT_PTR)FALSE;
}

//{{NO_DEPENDENCIES}}
// Microsoft Visual C++ generated include file.
// Used by ComputeRealDeterminant.rc

#define IDS_APP_TITLE			103

#define IDR_MAINFRAME			128
#define IDD_COMPUTEREALDETERMINANT_DIALOG	102
#define IDD_ABOUTBOX			103
#define IDM_ABOUT				104
#define IDM_EXIT				105
#define IDI_COMPUTEREALDETERMINANT			107
#define IDI_SMALL				108
#define IDC_COMPUTEREALDETERMINANT			109
#define IDC_MYICON				2
#ifndef IDC_STATIC
#define IDC_STATIC				-1
#endif
// Next default values for new objects
//
#ifdef APSTUDIO_INVOKED
#ifndef APSTUDIO_READONLY_SYMBOLS

#define _APS_NO_MFC					130
#define _APS_NEXT_RESOURCE_VALUE	129
#define _APS_NEXT_COMMAND_VALUE		32771
#define _APS_NEXT_CONTROL_VALUE		1000
#define _APS_NEXT_SYMED_VALUE		110
#endif
#endif

#define IDD_DATA_INPUT_DIALOG		1000
#define IDC_COMBO_N					1010
#define IDC_EDIT_MULTILINE1			1020
#define IDC_EDIT_MULTILINE2			1030
#define IDC_BUTTON_COMPUTE			1040
#define IDM_START					32771

//Microsoft Visual C++ generated resource script.
//
#include "resource.h"

#define APSTUDIO_READONLY_SYMBOLS
/////////////////////////////////////////////////////////////////////////////
//
// Generated from the TEXTINCLUDE resource.
//
#ifndef APSTUDIO_INVOKED
#include "targetver.h"
#endif
#define APSTUDIO_HIDDEN_SYMBOLS
#include "windows.h"
#undef APSTUDIO_HIDDEN_SYMBOLS
/////////////////////////////////////////////////////////////////////////////
#undef APSTUDIO_READONLY_SYMBOLS

#if !defined(AFX_RESOURCE_DLL) || defined(AFX_TARG_ENU)
LANGUAGE 9, 1

/////////////////////////////////////////////////////////////////////////////
//
// Icon
//

// Icon with lowest ID value placed first to ensure application icon
// remains consistent on all systems.

IDI_COMPUTEREALDETERMINANT       ICON         "ComputeRealDeterminant.ico"
IDI_SMALL               ICON         "small.ico"

/////////////////////////////////////////////////////////////////////////////
//
// Menu
//

IDC_COMPUTEREALDETERMINANT MENU
BEGIN
POPUP "&Begin"
BEGIN
    MENUITEM "&Start", IDM_START
    MENUITEM SEPARATOR
    MENUITEM "E&xit", IDM_EXIT
END
POPUP "&Help"
BEGIN
    MENUITEM "&About ...", IDM_ABOUT
END
END


/////////////////////////////////////////////////////////////////////////////
//
// Accelerator
//

IDC_COMPUTEREALDETERMINANT ACCELERATORS
BEGIN
    "?",            IDM_ABOUT,              ASCII,  ALT
    "/",            IDM_ABOUT,              ASCII,  ALT
END


/////////////////////////////////////////////////////////////////////////////
//
// Dialog
//

IDD_ABOUTBOX DIALOGEX 0, 0, 170, 62
STYLE DS_SETFONT | DS_MODALFRAME | DS_FIXEDSYS | WS_POPUP | WS_CAPTION | WS_SYSMENU
CAPTION "About ComputeRealDeterminant"
FONT 8, "MS Shell Dlg"
BEGIN
    ICON            IDI_COMPUTEREALDETERMINANT,IDC_STATIC,14,14,21,20
    LTEXT           "ComputeRealDeterminant, Version 1.0",IDC_STATIC,42,14,114,8,SS_NOPREFIX
    LTEXT           "Copyright (c) 2026",IDC_STATIC,42,26,114,8
    DEFPUSHBUTTON   "OK",IDOK,113,41,50,14,WS_GROUP
END

IDD_DATA_INPUT_DIALOG DIALOGEX 0, 0, 280, 260
STYLE DS_SETFONT | WS_POPUP | WS_CAPTION | WS_SYSMENU
CAPTION "Data Input Dialog"
FONT 10, "Courier New", 700
BEGIN
LTEXT       "n:", IDC_STATIC, 10, 10, 30, 10
COMBOBOX    IDC_COMBO_N, 70, 10, 50, 60, CBS_DROPDOWNLIST
| WS_VSCROLL | WS_TABSTOP
LTEXT       "input matrix:", IDC_STATIC, 10, 30, 200, 10
LTEXT       "determinant:", IDC_STATIC, 10, 185, 200, 10
PUSHBUTTON  "Compute", IDC_BUTTON_COMPUTE, 10, 220, 50, 16
PUSHBUTTON  "Cancel", IDCANCEL, 220, 220, 50, 16
END

/////////////////////////////////////////////////////////////////////////////
//
// DESIGNINFO
//

#ifdef APSTUDIO_INVOKED
GUIDELINES DESIGNINFO
BEGIN
    IDD_ABOUTBOX, DIALOG
    BEGIN
        LEFTMARGIN, 7
        RIGHTMARGIN, 163
        TOPMARGIN, 7
        BOTTOMMARGIN, 55
    END
END
#endif    // APSTUDIO_INVOKED

#ifdef APSTUDIO_INVOKED
/////////////////////////////////////////////////////////////////////////////
//
// TEXTINCLUDE
//
1 TEXTINCLUDE
BEGIN
    "resource.h\0"
END

2 TEXTINCLUDE
BEGIN
    "#ifndef APSTUDIO_INVOKED\r\n"
    "#include ""targetver.h""\r\n"
    "#endif\r\n"
    "#define APSTUDIO_HIDDEN_SYMBOLS\r\n"
    "#include ""windows.h""\r\n"
    "#undef APSTUDIO_HIDDEN_SYMBOLS\r\n"
    "\0"
END

3 TEXTINCLUDE
BEGIN
    "\r\n"
    "\0"
END

#endif    // APSTUDIO_INVOKED

/////////////////////////////////////////////////////////////////////////////
//
// String Table
//

STRINGTABLE
BEGIN
   IDC_COMPUTEREALDETERMINANT   "COMPUTEREALDETERMINANT"
   IDS_APP_TITLE       "ComputeRealDeterminant"
END

#endif
/////////////////////////////////////////////////////////////////////////////



#ifndef APSTUDIO_INVOKED
/////////////////////////////////////////////////////////////////////////////
//
// Generated from the TEXTINCLUDE resource.
//

/////////////////////////////////////////////////////////////////////////////
#endif    // not APSTUDIO_INVOKED