25 votes

How can I quickly judge whether matrix A is the inverse matrix of B?

You might be looking for something like Freivalds' algorithm. It is a randomized probabilistic algorithm that given three square matrices $A,B$ and $C$ checks if $A \times B = C$ by using random ...
user avatar
  • 606
24 votes

Real life examples of *zero* weight edges in graphs

Of course. The weight can mean things that are irrelevant to the existence of an edge. Since you don't ask for a "list of say 6 or 7 real-life examples", I will just add one. Consider a ...
user avatar
  • 13.2k
17 votes

How to prove that matrix inversion is at least as hard as matrix multiplication?

If you want to multiply two matrices $A$ and $B$ then observe that $$\begin{pmatrix}I_n&A&\\&I_n&B\\&&I_n\end{pmatrix}^{-1}= \begin{pmatrix}I_n&-A&AB\\&I_n&-B\\&...
user avatar
  • 1,116
13 votes
Accepted

Fastest way to solve a system of linear equations

A LU decomposition of a $n \times n$ matrix can be computed in $O(M(n))$ time, where $M(n)$ is the time to multiply two $n \times n$ matrices. Therefore, you can find a solution to a system of $n$ ...
user avatar
  • 140k
12 votes

Real life examples of *zero* weight edges in graphs

The classic strategy game Civilization by MicroProse represents the world map as a square grid where each node of the grid is a tile of the world map, representing some type of terrain. Players ...
user avatar
  • 966
11 votes
Accepted

Minimal basis for set of binary vectors using XOR

If you treat your vectors as over the field $GF(2)$ rather than over the set $\{0,1\}$, then what you ask is to find a basis for the span of a set of vectors. This is a well-studied problem in linear ...
user avatar
9 votes

Real life examples of *zero* weight edges in graphs

In circuity, we often construct a graph of a circuit. Wires are typically modeled as 0 resistance because, frankly, measuring the resistance of wires is really tricky and rarely profitable. So if we ...
user avatar
  • 3,025
8 votes

Automated optimization of 0-1 matrix vector multiplication

This is related to an open research question, which is known as the "Online Boolean Matrix-Vector Multiplication (OMv) problem". This problem reads as follows (see [1]): Given a binary $n \times n$ ...
user avatar
8 votes

How can I quickly judge whether matrix A is the inverse matrix of B?

tl;dr: You can make a rough probabilistic judgement in $O(1)$ time Let's assume you are willing to settle on a test which differentiates "good" matrices $A,B$ from "pretty bad" $A,...
user avatar
  • 937
7 votes
Accepted

Choosing nonzero entries from an array so no pair in same row or column

The Birkhoff–von Neumann theorem states that a doubly stochastic matrix (a matrix with non-negative entries in which rows and columns sum to 1) can be written as a convex combination of permutation ...
user avatar
7 votes

Why linear transformation can improve classification accuracy when the dimensionality of data is high?

Multiplying by the $n * p$ matrix decreases the dimensionality of the data set. Think of this as projecting the highly dimensional space into a smaller dimensional space. For example, you could do ...
user avatar
  • 248
7 votes
Accepted

Recursive definition of Matrix

Multiple Dimensions For a recursive counterpart for matrices, we need dependent types. Indeed, lists are one dimensional and so (horizontal) concatenation of lists is all that is needed. However, ...
user avatar
7 votes

Suitable choice for moderate-size square matrix multiplication?

Dumas and Pan recently wrote a non-asymptotic survey of fast matrix multiplication in practice, which hopefully answers your questions. They concentrate on matrices of order at most a million, and ...
user avatar
7 votes
Accepted

Find if there is matrix that satisfying the following conditions

Hint #1: Hint #2:
user avatar
  • 140k
6 votes
Accepted

Algorithm: Dimension increase in 1D representation of Square Matrix

There is a simple solution, but it requires a different 1D representation of your matrix $M$. You suppose it is stored in an arbitrarily long 1D array $A$, so that new elements can be added. Then the ...
user avatar
  • 19.1k
6 votes
Accepted

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

Let $G$ be the number of good vectors, and $B$ be the number of bad vectors. The proof shows that $G \geq B$, since the mapping from the bad vectors to the good ones is one-to-one. Since all vectors ...
user avatar
6 votes

Counting islands in Boolean matrices

Orlp gives a solution using $O(n)$ words of space, which are $O(n\log n)$ bits of space (assuming for simplicity that $n=m$). Conversely, it is easy to show that $\Omega(n)$ bits of space are needed ...
user avatar
6 votes

Lower Bound of Matrix Multiplication

Strassen, in his paper describing Strassen's algorithm (Gaussian elimination is not optimal) mentions the result of Klyuyev and Kokovkin-Shcherbak [1] that Gaussian elimination for solving a system ...
user avatar
6 votes

Given a row sum vector and a column sum vector, determine if they can form a boolean matrix

This problem is known as discrete tomography, and in your case two-dimensional discrete tomography. A nice approachable introduction is written Arjen Pieter Stolk's thesis Discrete tomography for ...
user avatar
  • 12.3k
5 votes
Accepted

Is matrix "adjoint-squaring" faster than general matrix multiplication?

It's not faster (asymptotically). You can reduce general matrix multiplication down to three "adjoint-squarings". Suppose we're given an adjoint-squaring function $\mathfrak{F}$ where $\mathfrak{F}(M)...
user avatar
  • 5,722
5 votes
Accepted

Automated optimization of 0-1 matrix vector multiplication

If it is possible try to exploit banded tridiagonal nature of matrix. Otherwise if the matrix contains only a constant number of distinct values (which surely is being binary), you should try Mailman ...
user avatar
  • 9,325
5 votes
Accepted

Common idea in Karatsuba, Gauss and Strassen multiplication

The classical framework is the one of bilinear algorithms and tensor rank decompositions; basically, you construct the 3-way tensor associated to the bilinear map $f(A,B) = A \cdot B$, in the basis of ...
user avatar
5 votes
Accepted

Are there parallel matrix exponentiation algorithms that are more efficient than sequential multiplication?

If you have multiple processors that can work in parallel, then you can calculate any power up to the power (2^k) in k steps. For example: To calculate $M^{15}$, you calculate: Stage 1: Calculate $M^...
user avatar
  • 24.9k
5 votes
Accepted

Finding trading cycles

I'm assuming that items are always traded 1-for-1. How do I find the longest possible series (or path) of supply & demand matching among some people and therefore can foster an exchange?" If ...
user avatar
  • 497
5 votes

Fastest way to solve a system of linear equations

There is what you want to achieve, and there is reality, and sometimes they are in conflict. First you check if your problem is a special case that can be solved quicker, for example a sparse matrix. ...
user avatar
  • 24.9k
5 votes

How does matrix chain multiplication problem has an optimal substructure?

First of all, it is correct and important to know that optimal solutions need not necessarily be unique! However, this doesn't mean we cannot have optimal substructure. Recall what optimal ...
user avatar
  • 6,978
4 votes

How to use different size features in SVM?

I think you have a misconception. SVM does not necessarily give the latter 58 features a weight of 58/59. Rather, SVM learns what weights to use for each feature, based upon what helps it build the ...
user avatar
  • 140k
4 votes

How to reduce the low-rank matrix completion problem to integer programming?

Simplifying the problem: Given a positive integer $r$ positive integers $m, n \geq 2$ a partial binary matrix $\mathrm A \in \{*, 0,1\}^{m \times n}$ (where $*$ denotes an unknown entry)...
user avatar
4 votes

Are there any non-naive parallel sparse matrix multiplication algorithms?

This recent paper proposes a different approach, based on hypergraph partitioning. Grey Ballard, Alex Druinsky, Nicholas Knight, and Oded Schwartz. 2015. Brief Announcement: Hypergraph Partitioning ...
user avatar
4 votes

Time complexity of comparing two $N \times N$ Matrices?

A very simple adversary argument shows that when comparing two vectors of length $M$ (in your case, $M = N^2$), you must query (in the worst case) all positions of both vectors to know whether they ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible