# Tagged Questions

The tag has no usage guidance.

19 views

### Complexity of matrix inverse via Gaussian elimination

I'm trying to determine the exact complexity of finding an $n\times n$ matrix inverse of $A$. If it is known that the complexity of Gaussian elimination is $\frac{2}{3}n^3 + \frac{1}{2}n^2+O(n)$, then ...
38 views

### Permutation on matrix to fill main diagonal with non-zero values

I am currently working on some sparse non-singular matrices. One of the algorithms I use requires divisions by the elements on the main diagonal so I have to ensure that my main diagonal is filled ...
127 views

### is this NPC Prob? Minimum count of distinct values at all matrix columns provided only in-row swap operation

I am searching for an algorithm for this! Cannot find anything useful in textbook so far. Thanks in advance! Question: The input is a $N \times K$ matrix, where $N$ and $K$ are positive numbers( ...
21 views

### How do Perwitt and Sobel detect edges?

I read up on the Perwitt operator and it detects two types of edges (vertical and horizontal). The Sobel operator on the other hand does the same as the Perwitt except that the masks are not constant ...
32 views

### Is this a known question in matrix sketching?

Say one has a $D \times n$ matrix $A$ all of whose entries are non-zero. One wants a method which will look at each of the columns of $A$ one by one and create new $m << D$ dimensional columns ...
27 views

### Where is pivoting done in the Crout decomposition algorithm?

Consider the following code, found on wikipedia, that implements the Crout decomposition algorithm: ...
65 views

### How to determine Isomorphism of Non-Symmetric Matrix when Permutation-Set is given?

Consider, two $m \times n$ matrices $A, B$ such that there is a permutation $\kappa$ that such that such that $A^{\kappa}=B$ (Wielandt's notation), i.e. $A, B$ are isomorphic but not equal. Since,...
27 views

### What is the Time Complexity of the Matrix Exponential?

While trying to compute the Matrix Exponential of an nxn array I decided to take advantage of a Python function called ...
28 views

### Generate a graph to exact size using Kronecker product graph model

In network science, we can take sample a complex system and derive from this sampling a representative network (or graph) that describes the system to some extent. A model of a network, is a powerful ...
60 views

### Recursive definition of Matrix

Like Linked-list for Array, is there a recursive counter-part for Matrix? Is there a persistent data structure which can be used in place of Matrix in pure functional language like Haskell?
44 views

### How does RAID-5 algorithm locate the right device?

Please consider the following diagram of a RAID-5 array (Ignore the gray background): Now, given a logical address, how can one return the device number (0-3)? For example, DeviceByLogicalSector(50)...
50 views

37 views

### 3D Column Sort (Leighton) Algorithm

Suppose you have a matrix A (9x3) of Real numbers and want to sort in columnwise. In this case we can use Leighton ColumnSort algorithms to achieve this. But question is, how can I sort 3 dimensional ...
91 views

### Correctness of Freivald algorithm for checking matrix multiplication, why is the probability of checking $AB \neq C$ at least 1/2?

I am going to consider Freivald's algorithm in the field mod 2. So in this algorithm we want to check wether $$AB = C$$ and be correct with high probability. The algorithm choose a random $r$ n-...
40 views

### Arden's rule expressed as matrix algebra

The following theorem is (in the context of languages) known as Arden's Lemma: Given a linear system $X = B+AX$ and the matrix A is quasiregular, then we have a solution which is unique and which ...
111 views

### Looking for an algorithm to iterate over essentially different solutions

I'll explain my problem with an analogy to Sudoku-grids. Consider a filled Sudoku-grid. If you exchange labels or rearrange rows/columns within a block, you have another valid Sudoku-grid. However ...
28 views

### Find all paths of length k [duplicate]

I have an adjacency matrix, call it A, representing a directed graph. I want to find all paths of length k. I know that A^k ...
26 views

367 views

### Most time-optimal parallel algorithms to calculate the determinant and inverse of a matrix

I am writing a numeric library to exploit GPU massive parallelism and one of the implemented primitives is a matrix class. Naturally I require a determinant and inverse function for this class and I ...
95 views

### Fast checking Matrix multiplication in mod 10

I recently faced this problem in a programming contest: Given 3 square matrices N x N of size N up to 1000. All elements in 3 matrices are from 0 to 9. Check if matrix A x B equals to C, mod 10. In ...