Are you bound to using datatypes and not bits? You seem to have only -- off/on -- for each "cell" in your matrix.
This has O(N) access to columns given a row, or to rows given a column.
Code:
// proof of concept
#include <stdlib.h>
#include <stdio.h>
#include <limits.h>
static unsigned char table[512][64]={{0x0}}; // 512 x 512 bitmap
void setrowcol(int col, int row) // set one cell to X
{
int bit=col % CHAR_BIT;
col/=64; // which element of array
table[col][row]|=(1<<bit);
}
int getrowcol(int col, int row) // set one cell to X
{
int bit=col % CHAR_BIT;
col/=64; // which element of array
return !! (table[col][row] & (1<<bit)); // 1 or zero
}
int main()
{
int col, row;
srand(time(NULL));
col=rand()%512;
row=rand()%512;
setrowcol(col,row);
printf(" table[row=%d][col=%d]=%d\n", row, col, getrowcol(col, row) );
col/=2;
row/=2;
printf(" table[row=%d][col=%d]=%d\n", row, col, getrowcol(col, row) );
return 0;
}