2
votes
1answer
28 views

Checking connectivity of adjacency matrix

What do you think is the most efficient algorithm for checking whether a graph represented by an adjacency matrix is connected? In my case I'm also given the weights of each edge. There is another ...
0
votes
1answer
35 views

Find longest vector by summing some vectors in given set

Given $n$ vector $(x_1, y_1), (x_2, y_2),(x_3, y_3),\dots,(x_n,y_n)$. Find a subset S of vector such that $\text{}\left |\sum_{v\in S} v\right |$ Sorry for my English. Please give me a hint how to ...
0
votes
1answer
17 views

Finding end point of straight line given starting point and angle

I have a program which computes the angle of skew of a scanned photograph. It returns the angle of skew in degrees. I now need to draw lines across the image which follow the angle of skew. These ...
1
vote
1answer
11 views

Algorithm to find out on which position ZX is?

I am having the following problem. Lets consider the alphabet. From A-Z there are 26 letters. If its for example AA, then its ...
4
votes
1answer
112 views

Bipartite graph matching like problem.

Let $A=\{a_1,a_2, ..., a_n \}$ and $B=\{b_1,...,b_m\}$ be finite sets. Also $A_1,...,A_k\subset A$ are covering of $A$ and $B_1,...,B_t\subset B$ are covering of $B$. Let $V$ be a set of pairs of ...
3
votes
2answers
76 views

How to extend an existing orthogonal set of vectors?

Suppose I have $k$ vectors in $\mathbb R^n$ that are orthogonal to each other ($k \ll n$). Is there an efficient way to find another vector that is orthogonal to all these given vectors? If we put ...
1
vote
0answers
19 views

Minimize the number of nonzero elements of a matrix through elementary row operations?

Is there a general method to minimize the number of nonzero elements of a real rectangular matrix through elementary row operations? I am looking for something analogous to Gaussian elimination, that ...
2
votes
1answer
38 views

Determining the ratios needed in gear reduction

I am trying to work out the math behind building a gear box for turning a gear a specific RPM from a small motor. Given that a typical DC hobby motor turning at 200 RPM, and a target in the final ...
4
votes
0answers
19 views

Decoding of Gabidulin code

Consider the space of matrices in $\mathbb{F}_q^{n \times m}$ where $\mathbb{F}_q$ is the finite field with $q$ elements. We can define a metric on this space, given by $d(A,B) := rank(A-B)$, called ...
1
vote
1answer
40 views

How to find the size of the largest collection of orthogonal rows

Given a non-square matrix $M$ over the reals, how can you find the size of the largest collection of orthogonal rows?
0
votes
0answers
26 views

Algorithmic Complexity of Linear Independence

Given n m-dimensional vectors. You can determine linear independence by Gaussian elimination. http://en.wikipedia.org/wiki/Gaussian_elimination#Computational_efficiency Checking linear independence ...
1
vote
2answers
51 views

Matrix decomposition definition

Wikipedia says "In the mathematical discipline of linear algebra, a matrix decomposition or matrix factorization is a factorization of a matrix into a product of matrices. There are many different ...
1
vote
2answers
42 views

Number of solutions for inqeuality

Is there a way we can determine number of solutions for equation $$x*y < d$$ where d is constant and x & y are positive integers greater than 1. I am not interested in actual values, but ...
0
votes
0answers
26 views

Matrix Partial Derivative?? NMF Multiplicative update rules

Recently, I read Lee & Seung's work on Nonnegative Matrix Factorization. But I have problem with the update rule: The object function is minimize: $\|V - MH \|$ with respect to M and H, subject ...
0
votes
0answers
21 views

Iteratively solve linear equations with rank-1 updates on LHS and RHS

What is the best way to iteratively solve updating equations of the form $$ Ax=b $$ $$ (A+c_1v_1^\intercal)x_1=b+ \alpha_1 d_1 $$ $$ (A+c_1v_1^\intercal+c_2v_2^\intercal)x_2=b+\alpha_1d_1+\alpha_2d_2 ...
5
votes
0answers
123 views

Generating a stochastic matrix with a given second dominant eigenvalue

I need a procedure (iterative or otherwise) that, given a positive integer $N$ and a (possibly complex) number $\lambda$ such that $0 < \vert \lambda \vert < 1$, will be able to generate an $N ...
4
votes
1answer
45 views

Randomly generate an matrix $A$ s.t. $A^m = I$

Fixed $n$, I want to randomly generate a $n \times n$ real matrix $A$ from the set: $\{A \in \mathcal{M}_{n \times n}(\mathbb{R}): \exists m \in \mathbb{N} \mbox{ s.t. } A^m = I\}$ I think I should ...
1
vote
1answer
34 views

matrix row/col mapping

Many square matrices are symmetric. i.e. $a_{i,j}=a_{j,i}$ For such matrices, we can only store the upper triangle elements, i.e. any $a_{i,j}$ for which $i<=j$. Assume a 10x10 matrix. Using this ...
2
votes
2answers
49 views

Solve linear equation system $A'Ax=A'Bz$

For $A$ and $B$ known matrices which are not square matrices, I have the following equation sistem i would like to solve numerically \begin{equation} A'Ax=A'Bz \end{equation} I want to know which is a ...
2
votes
2answers
87 views

Avoid dividing by zero with just variables and basic operators

I am working on stats for a sports team, and one of the stats I have the ratio of Shots and Shots on Target (Which I call ...
1
vote
1answer
31 views

Fast method to detect if a circulant matrix is singular

I have to write some code to detect if a large number of smallish (less than 20 by 20) square 0-1 matrices are singular over $\mathbb{R}$. As a circulant matrix is defined by its first row and its ...
2
votes
2answers
56 views

Linear Diophantine equation in two variables with additional constraints

Given, $$aX + bY = c$$ where, $$c > b > a > 0;\quad X, Y > 0;\quad b\nmid c, a\nmid c$$ I want to find out if a solution exists as efficiently as possible (I'm not interested ...
0
votes
1answer
68 views

How to tell if there exists a vector orthogonal to half your vectors

Given a set of $N$ vectors each with $n$ entries from the integers. How can you determine efficiently if there is any non-zero vector in $\mathbb{R}^n$ which is orthogonal to half of them?
2
votes
2answers
196 views

Flood algorithm - find polygon containing a given point.

I have some code that represents a set of a set of interconnected line segments in 2D, in pseudo-code it'd be like this: ...
1
vote
1answer
83 views

Solve $Mx = 0$ for $x$

Given an $m$ by $n$ matrix $M$ whose elements are $0$ or $1$, is there an efficient way of finding a vector $x \ne 0$ whose are elements are from $-1,0,1$ such that $Mx = 0$, or even determining if ...
0
votes
0answers
76 views

Strassen's Matrix Multiplication Example Problem

How to multiply two matrices using strassen's matrix multiplication.I have only learned the theory part but i cannot find any examples on the net. Could some one explain with two 2X2 Matrices.
29
votes
6answers
2k views

The milk sharing problem

I found a book with math quizzes. It was my father's when he was young. I encountered a problem with the following quiz. I solved it, but I wonder, is there a faster way to do it? If so, how can I ...
0
votes
0answers
27 views

Levenberg-Marquardt algorithm

Does anyone know if the Levenberg-Marquardt algorithm used to solve non-linear least squares problems has any regularization process?
1
vote
0answers
45 views

Gauss-seidel and implicit method

I have a matrix $\mathbf{X}$ and I want to apply a function $f_{ij}$ to each entry of it, until convergence is satisfied. If a value is known in this matrix, then the $f_{ij}$ at this point may be the ...
2
votes
0answers
563 views

Determinant of symmetric tridiagonal matrices

Given an $n\times n$ tridiagonal matrix $$A =\left(\begin{array}{ccccccc} ...
6
votes
0answers
125 views

Algorithm for obtaining the surface of a mirror

My colleague and I have been trying to implement an algorithm described in the paper "Recovering local shape of a mirror surface from reflection of a regular grid", primary author of which being ...
1
vote
1answer
77 views

Efficient Algorithm for Generalized Sylvester's Equation

Is there an efficient computational algorithm for solving the generalized Sylvester's equation: $\displaystyle \sum_{i=1}^{n}A_{i}XB_{i}=C$ The conventional Kronecker product approach to solve this ...
1
vote
1answer
74 views

Proof for existence of exactly one solution for the number of marbles in each box

There are four boxes A, B, C and D containing marbles. Two boxes are randomly selected and the number of marbles in each box is summarized. This procedure is repeated five times with the ...
0
votes
1answer
70 views

Finding the “middle 2” of four lines

This may seem like an overly abstract problem, but it's the best generalization I could make of a specific problem I'm trying to tackle. This problem works in 2-dimensional Euclidean space. A ...
0
votes
0answers
44 views

Operation count for Tridiagonal System

What is the operation count for solving the tridiagonal system $Ax=b$. I would guess it is $O(n^2)$ because all we are doing is making one sub-diagonal zero all the way across giving us $t(n)=n$ and ...
3
votes
0answers
64 views

How to quickly approximate the eigenvectors of a symmetric matrix

Given a symmetric $n \times n$ matrix $A$, is there any algorithm that can quickly approximate all of its eigenvectors? By "quickly", I mean with time complexity less than $\mathcal{O}(n^3)$.
2
votes
0answers
85 views

Does a matrix represent a bijection

We have a square binary matrix that represents a connection from rows to columns. Is there a way to tell if a bijection exists (other than checking for all possible bijections and iterating through ...
1
vote
2answers
40 views

Solving system of linear eqaution in special cases

I have to solve for $Ax=B$. Here the diagonal elements of $A$ are $-1$ and all other elements are $1$. $A$ is $n \times n$ matrix . In this special case can we solve for $x$ quickly? EDIT: quick is ...
1
vote
1answer
124 views

Computing the number of positive and negative eigenvalues

Given a $n \times n$ symmetric matrix $A$ with integers as entries I would like to compute the number of strictly negative $\rm{nn}(A)$ and positive $\rm{np}(A)$ eigenvalues of $A.$ My question is ...
1
vote
1answer
469 views

Prove Solving a Lower Triangular Matrix By Forward Substitution is Backwards Stable

I'm taking a class in scientific computing and we are working on proving stability of certain algorithms. Unfortunately, at this stage, everything is proof-based, and I have little to no experience in ...
0
votes
0answers
39 views

Probability, linear independence and study of variant of Lights Out

Using Arduino, some leds and pushbuttons I've created a simple variant of the mathematically popular game "Lights Out". In my variant, the starting configuration is always all lights on; what changes ...
1
vote
1answer
55 views

Meet of lines in n-dimension.

I am searching for a general approach to use in a script for determining if two n-dimensional lines represented by one point and their direction vector are skew, parallel, intersecting or identical. ...
0
votes
2answers
106 views

modulo 2 linear equation algorithm

Given is a set of modulo 2 linear equations. I'm looking for a performant algorithm that solves these linear equations. The Row Reduction to the ...
0
votes
1answer
46 views

Project path on tiled surface

Here is the description. I do present earth as a Sphere. I've splitted the earth on tiles starting from latitude=0, longitude=0. Tile is a rectangle ~$50\times50$ kilometers. Tiles are "planar". ...
0
votes
1answer
96 views

Payment problem

I'm looking for an algorithm, which can solve the following problem: There is a basket, containing (n) products, paired with a value, which shows how much money is required to cover them. E.g ...
2
votes
1answer
164 views

Find a projection of a $k$-simplex with minimal “radius”

Let $S$ be a $k$-simplex in $\mathbb{R}^k$. I'd like to find a hyperplane $P$ that passes through the origin such that projections of vertices of $S$ onto $P$ are as close as possible to the origin ...
2
votes
1answer
55 views

How to compute $x$ and $y$

How can one find in an efficient way $x,y \in \mathbb{Z}$ with max$\{|x|,|y|\} > 0$ as small as possible such that $\mid \pi x + e y \mid < 10^{-4}$ ? I have reduced the following lattice ...
0
votes
2answers
247 views

Find a solution to any single-variable equation

I know it is not possible to solve any equation of fifth degree and higher "using only a finite combination of the arithmetic operations and radicals in terms of the coefficients" (see on Wikipedia). ...
1
vote
1answer
36 views

Question about linear systems of equations

Let $X=\{x_1,\cdots,x_n\}$ be a set of variables in $\mathbb{R}$. Let $S_1$ be a set of linear equations of the form $a_1 x_1+\cdots+a_n x_n=b$ that are independent. Let $k_1=|S_1|<n$ where $|S_1|$ ...
1
vote
0answers
58 views

Checking if a binary vector lies in the affine span of given binary vectors

Let $x_1, \ldots,x_N \in \{0,1\}^D$ be $N$ binary vectors, assumed affinely independent (in the field of reals). Is there an efficient algorithm for determining whether a new binary vector $x_{N+1}$ ...