\[ \int \frac{(x-1)\sqrt{x^4+2x^3 +4x^2+2x+1}}{x^2(x+1)}dx \]
Ewwwwwwwwwwww. That's probably the worst I've seen
(what a great christmas gift lol)
I'm not going to write out the full working for the Gaussian integral stuff because I'm so tired, but I'll write some brief notes. Perhaps someone can finish it off
_______________________________________________________________
Define \[I_n(\alpha)=\int_{-\infty}^\infty x^ne^{-\alpha x^2}dx,\quad\alpha>0,\ n\in\mathbb{N}.\] We are given that \(I_0(1)=\sqrt{\pi}\) and so by scaling \(x\) appropriately, we find that \[I_0(\alpha)=\sqrt{\frac{\pi}{\alpha}}.\]Now, note that if \(n\) is odd, then the integrand is an odd function, and so \[I_{2k-1}(\alpha)\equiv0,\quad k\in\mathbb{N}.\] Therefore, we consider even \(n\).
Making use of the fact that \[I_n(\alpha)=-\frac{\partial}{\partial\alpha}\big[I_{n-2}(\alpha)\big],\]we find that for even \(n\), \[I_n(\alpha)=\frac{(n-1)!!}{(2\alpha)^{n/2}}\sqrt{\frac{\pi}{\alpha}}.\] Substituting in \(\alpha=1\) gives us the final result of \[\int_{-\infty}^\infty x^ne^{-x^2}dx=\begin{cases}0 & \text{odd }n\\ \dfrac{(n-1)!!}{2^{n/2}}\sqrt{\pi} & \text{even }n\end{cases},\quad n\in\mathbb{N}.\]
_______________________________________________________________
But I just wanted to put up some C code for problem set 2 because I thought it was a fun programming exercise.
// Finds and prints the first matrix that works
// If none exists, mention that none exists
// Designed specifically for matrices over Z_2
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Size of matrix - can be changed
#define SIZE 4
typedef struct matrixRep *Matrix;
typedef struct matrixRep {
int mm[SIZE][SIZE];
} _matrix;
Matrix newMatrix();
void destroyMatrix(Matrix m);
unsigned long long maxNumIterations(unsigned int size);
void matrixInit(Matrix m, int i);
void idInit(Matrix id);
void kkInit(Matrix k);
bool matrixCmp(Matrix a, Matrix b);
Matrix matrixAdd(Matrix a, Matrix b);
Matrix matrixMult(Matrix a, Matrix b);
Matrix matrixCube(Matrix m);
Matrix matrixFourth(Matrix m);
void printMatrix(Matrix m);
int main() {
Matrix m, mcubed, mfourth, msum;
Matrix id, kk;
unsigned long long n = maxNumIterations(SIZE);
bool found = false;
id = newMatrix();
idInit(id);
kk = newMatrix();
kkInit(kk);
m = newMatrix();
for (unsigned long long i = 0; i < n; i++) {
if (found) break;
matrixInit(m, i);
mcubed = matrixCube(m);
msum = matrixAdd(mcubed, m);
mfourth = matrixFourth(m);
if (matrixCmp(msum, kk) && matrixCmp(mfourth, id)) found = true;
destroyMatrix(mcubed);
destroyMatrix(msum);
destroyMatrix(mfourth);
}
if (found) {
printf("Found matrix:\n");
printMatrix(m);
printf("\n");
} else {
printf("Not found.\n");
}
destroyMatrix(id);
destroyMatrix(kk);
destroyMatrix(m);
return 0;
}
// newMatrix: allocates memory for a new matrix
Matrix newMatrix() {
Matrix new = calloc(1, sizeof(struct matrixRep));
return new;
}
// destroyMatrix: frees up memory associated with a matrix
void destroyMatrix(Matrix m) {
free(m);
}
// maxNumIterations: computes 2^(size^2) - the max amount of times
// the loop in the main function can run for
unsigned long long maxNumIterations(unsigned int size) {
unsigned long long n = 1;
unsigned long int sizeSq = size*size;
for (unsigned long int i = 0; i < sizeSq; i++) {
n <<= 1;
}
return n;
}
// matrixInit: sets up m for the current value of i in the main function's loop
void matrixInit(Matrix m, int n) {
int mask = 1;
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
m->mm[i][j] = n & mask;
mask <<= 1;
m->mm[i][j] = (m->mm[i][j] == 0) ? 0 : 1;
}
}
}
// idInit: sets up the identity matrix
void idInit(Matrix id) {
int posOfOne = 0;
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
if (j == posOfOne) id->mm[i][j] = 1;
else id->mm[i][j] = 0;
}
posOfOne++;
}
}
// kkInit: sets up the matrix of 1's
void kkInit(Matrix k) {
for (int i = 0; i < SIZE; i++)
for (int j = 0; j < SIZE; j++)
k->mm[i][j] = 1;
}
// matrixCmp: checks if two
bool matrixCmp(Matrix a, Matrix b) {
bool same = true;
for (int i = 0; i < SIZE; i++) {
if (!same) break;
for (int j = 0; j < SIZE; j++) {
if (a->mm[i][j] != b->mm[i][j]) {
same = false;
break;
}
}
}
return same;
}
// matrixAdd: computes the sum of two matrices
Matrix matrixAdd(Matrix a, Matrix b) {
Matrix sum = newMatrix();
for (int i = 0; i < SIZE; i++)
for (int j = 0; j < SIZE; j++)
sum->mm[i][j] = a->mm[i][j] ^ b->mm[i][j];
return sum;
}
// matrixMult: computes the product of two matrices
Matrix matrixMult(Matrix a, Matrix b) {
Matrix prod = newMatrix();
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
for (int k = 0; k < SIZE; k++)
prod->mm[i][j] += a->mm[i][k] * b->mm[k][j];
prod->mm[i][j] &= 1;
}
}
return prod;
}
// matrixCube: computes the cube of a matrix
Matrix matrixCube(Matrix m) {
Matrix msq = matrixMult(m, m);
Matrix mcb = matrixMult(msq, m);
destroyMatrix(msq);
return mcb;
}
// matrixFourth: computs the fourth power of a matrix
Matrix matrixFourth(Matrix m) {
Matrix msq = matrixMult(m, m);
Matrix mfr = matrixMult(msq, msq);
destroyMatrix(msq);
return mfr;
}
// printMatrix: displays a matrix to stdout
void printMatrix(Matrix m) {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++)
printf("%d ", m->mm[i][j]);
printf("\n");
}
}
...but then soon enough I realised how shit this code was because it's an \( \mathcal{O}(2^{n^2}) \) algorithm (slow when \(n=5\)) wonder if improvements can be made to it. I know that right now it's checking matrices which aren't of full rank which is redundant. Anyone got suggestions on some easy math that I can probably convert into code to make it faster?
Yeah, it just grows
super really really really fast lol. When I got this problem I did have a think about how to search efficiently, but failed horribly because I'm a terrible programmer. Here were my thoughts nonetheless:
First, take your \(n\times n\) matrix for even \(n\) and form a binary number by taking each row of the matrix and placing them next to each other. That is, \[M=\begin{bmatrix}m_{11} & \dots & m_{1n}\\ \vdots & \ddots & \vdots\\ m_{n1} & \dots & m_{nn} \end{bmatrix}\ \ \text{becomes}\ \ D=\big[m_{11}...m_{1n}\dots m_{n1}...m_{nn}\big].\] Now, there's no point checking matrices that have zero rows or columns, so we can check the digits of \(D\) in blocks of \(n\) for any \(1\)'s. Clearly, if we start checking from \(M=0\) (corresponding to \(D=0\)), then we're going to be checking many matrices with zero rows, so, we should start checking from the lowest number \(D\) that contains at least a \(1\) in every row and column. That number would be formed from matrix with \(1\)'s only on the minor diagonal (with \(0\)'s everywhere else). Then, just start adding \(1\) to \(D\) and if the corresponding matrix contains no zero rows/columns, then check if \(M=M^3\) and \(M^4=I\) simultaneously.
Then again, I'm not sure this would have a great affect though :/